(C++: Heap Implementation)

In class, we covered the algorithms for an array-based heap implementation, paying attention only to the keys in the heap. To use a heap to implement a priority queue, you also need to keep track of elements associated with each key. (We want extract_min to give us the element with the highest priority. We may or may not care what the priority value is.) For this assignment, you are to implement a C++ heap class, which stores pairs , where each element and priority value is an int.

Please complete the below implementation of heap.h file. (Both the class declaration and the function implementations are in the .h file)

- Marks are assigned for correctness of each of the functions (including constructors) which you need to implement. - Marks are assigned for giving recursive implementations of trickleDown and trickleUp (downHeap and upHeap in the class notes).

- Do not make any changes to the given function declarations. - Complete the implementations of all incompletely implemented functions. - You may add private functions if you find it useful.

/****************************************************** Heap.h -- Declarations for Basic Heap-of-Pair-of-Ints Class Stores pairs  of ints. Supports O(log n) insertion, O(1) peeking at min priority and element with min priority, and O(log n) extraction of element with min priority. *******************************************************/ using namespace std; class Heap{ public: // Constructors and Destructor // New empty Heap with default capacity. Heap(); // New empty Heap with capacity c. Heap(int c); // New Heap with size s, consisting of pairs  where, // for 0 <= i < s, Pi is Priorities[i] and Ei is value Elements[i]. // Capacity is s + c, where c is the "spare capacity" argument. // Requires: Priorities and Elements are of size at least s. Heap( const int * Priorities, const int * Elements, int s, int c); // New Heap with combined contents the two Heap arguments. // Size of the new Heap is the sum of the sizes of argument Heaps. // Capacity of the new Heap is its size plus the "spare capacity" c. Heap( const Heap & Heap1, const Heap & Heap2, int c ); // Destructor. ~Heap(); // Accessors bool empty() const {return hSize == 0;}; // True iff Heap is empty. int size() const { return hSize ;} ; // Current size of Heap. int capacity() const { return hCapacity ;} ; // Current capacity. int peekMin() const { return A[0].element ;} // Peek at minimum priority element. int peekMinPriority() const { return A[0].priority ;} // Peek at minimum priority. // Modifiers void insert( int element, int priority ); // Insert the pair . int extractMin(); // Remove and return the highest (minimum) priority element. private: class Pair{ public: int element ; int priority ; }; Pair* A ; // Array containing heap contents. int hCapacity ; // Max number of elements (= size of A). int hSize ; // Current number of elements. // Repairs ordering invariant after adding leaf at A[i]. void trickleUp(int i); // Repairs ordering invariant for sub-tree rooted at index i, // when A[i] may be have larger priority than one of its children, // but the subtrees of its children are heaps. void trickleDown(int i); // Establishes ordering invariant for entire array contents. void heapify(); //(Same as "make_heap" in lectures.) // Useful for implementing trickle up and down void swap(int i,int j); }; Heap::Heap(){ hCapacity = 10 ; A = new Pair[hCapacity]; hSize = 0 ; } Heap::Heap(int c){ // New empty Heap with capacity c. // Complete this. } // New Heap with capacity c+s, with s elements, consisting of pairs  where // Pi is Priorities[i], Ei is value Elements[i], for 0 <= i < s. Heap::Heap( const int * Priorities, const int * Elements, int s, int c){ // Complete this. } // New Heap with combined contents and of the two given heaps. Heap::Heap( const Heap & Heap1, const Heap & Heap2, int c ){ hCapacity = Heap1.hSize + Heap2.hSize + c ; // Complete this. } // Destructor Heap::~Heap(){ delete[] A; } // Modifiers void Heap::insert(int element, int priority){ A[hSize].element = element; A[hSize].priority = priority; trickleUp(hSize); hSize ++; } // Repairs the heap ordering invariant after adding a new element. // Initial call should be trickleUp(hSize-1). void Heap::trickleUp(int i){ // Complete this. } void Heap::swap(int i, int j){ Pair temp = A[i]; A[i] = A[j]; A[j] = temp ; } // Removes and returns the element with highest priority. // (That is, the element associated with the minimum priority value.) int Heap::extractMin(){ // Complete this. } // Repairs the heap ordering invariant after replacing the root. // (extractMin() calls trickleDown(0)). // (trickleDown(i) performs the repair on the subtree rooted a A[i].) // (heapify() calls trickleDown(i) for i from (hSize/2)-1 down to 0.) void Heap::trickleDown(int i){ // Complete this. } // Turns A[0] .. A[size-1] into a heap. void Heap::heapify(){ for( int i = (hSize/2)-1; i>=0 ; i-- ) trickleDown(i); } 

/************************************************************* Example Test Program for Basic Heap Class - Preliminiary Version. **************************************************************/ #include  #include "heap.h" using namespace std; void heapTest(); int main(){ heapTest(); return 0; } /* void Show( Heap & H, string s ){ cout << s << ".capacity=" << H.capacity() << endl; cout << s << ".size=" << H.size() << endl; cout << s << "=" ; H.display(); cout << endl; cout << "----------------------- "; } */ void heapTest(){ // Test default constructor and basic functions Heap H; H.insert(91,7); H.insert(92,6); H.insert(93,8); H.insert(94,5); H.insert(95,9); while( !H.empty() ){ cout << "min priority: " << H.peekMinPriority() << endl; cout << "min priority element: " << H.peekMin() << endl; H.extractMin(); } }