in C++

Implement a minimum heap of Item class with class priority queue

The smallest-priority item will be the root of the heap.

You need to implement two classes: (1) Item and (2) PriorityQueue Class Item will hold information for each item in the heap; it needs to have the following public data members and class constructor:

- Class PriorityQueue will have the following required data members and constructors:

Item() //default constructor

Item(int akey, int apriority)

int key; //a unique integer ID for each item

int priority; //an integer that is used to build a heap

PriorityQueue() //default constructor: creates arrays pointed to by aheap and keys of capacity 2.

PriorityQueue(Item *array, int length)

//takes a pointer to an input array with Item objects and length of array

// and build a heap from it using O(n)-time approach //Note: a user must create this array in the Heap prior to calling this constructor

//Need to check: if array is NULL, just return. Do not deallocate space for array.

//Important: first, check if aheap and keys are not NULL, then deallocate their space;

//then allocate space equal to length for aheap and keys, then copy items from array

//to aheap and populate keys, then build the heap by reheapifying downwards

//all nodes in the heap that are not leaves from right to left.

//Assume: keys inside array are correct you dont need to check this. ~PriorityQueue();

//destructor of the class: deallocates space taken by the heap private: Item* aheap = NULL;

//a pointer to an array that will be created in the heap of Item objects int *keys = NULL;

//a pointer to an array whose indices represent keys of Items in the heap,

//and keys[k] returns index j such that Item at aheap[j] has key equal to k. int size;

//total of items in the heap (smaller or equal to the length of the array) int capacity;

// the actual size (length) of the array, to which aheap points int totalKeys;

// the maximum number of keys that has been used in the heap In addition, you will implement the following public member functions of PriorityQueue: Member function Description Tests

int getCapacity() Returns capacity of aheap

int getSize() Returns the length (size) of the array, to which aheap points

void reheapifyUp(int i) This is a recursive function. Given an index of the array, it places the Item at that index into the correct position within the heap by recursively swapping with a parent if necessary

void reheapifyDown(int i) This is a recursive function that given an index of the array, it places the Item at that index i into the correct position within the heap by recursively swapping with the smallest of the two children (if children are equal, then swap with the left child)

void pop() Removes min-value from the heap, if the heap is empty, does not do anything.

Item getMin() Returns the min item in the heap (but does not remove it from the heap)

bool push(int akey, int apr) Given an object of class Item, it add this item to the heap. It needs to check the capacity of the heap: if the size of the heap is equal to its capacity, then this function must allocate new arrays in the Heap (increase capacity by 2, i.e. new capacity is twice as big as the old capacity), copy to these arrays the content from aheap and keys, and then deallocate space taken by the old aheap and keys and only then add a new item to the heap. Need to check: akey must be equal to the current (old) size. If it is not, return false (meaning the item was not enqueued into the heap).

bool updatePriority(int akey, int apr) Uses akey to find Item with this key and decrease this items priority to the new value equal to apr. Need to check: if apr is greater than the old priority, return false and do nothing. We only can decrease priorities in the Min-heap.

void print() Prints three lines: 1) priorities of items at indices 0, 1, 2, , size 1 of aheap 2) keys of items from left to right from the array pointed by aheap 3) indices stored in the array pointed by keys; print all keys starting with index 0 and ending with index totalKeys - 1 Format: value followed by space, and print endl after each line You will need this function for debugging