C++ Data Structures and Algorithms

Implementing a binary heap as a priority queue

By now, we should have a BinaryHeap class implementation as follows:

class BinaryHeap{private:    std::vector<int> vect;    int heapSize;    // three helper navigation function    int p(int i) { return i>>1; } // i/2    int l(int i) { return i<<1; } // i*2    int r(int i) { return (i<<1)+1; } // i*2+1    void ShiftUp(int index);    void ShiftDown(int i);public:    BinaryHeap();    bool IsEmpty();    void Insert(int key);    int ExtractMax();    int GetMax();};

We are going to create a priority queue using this BinaryHeap data structure. The following is the code snippet for the BinaryHeap data structure:

// Instantiate priority queueBinaryHeap * priorityQueue = new BinaryHeap();

Before we insert a new element, we can check whether ...