Priority Queue
In this task you have to implement a max priority queue using binary heap data structure. You need to implement the following functions:
1. Insert(x): Inserts an element into the priority queue according to the priority of its key. Time complexity: 𝑂(log𝑛).
2. FindMax(): Returns the element with largest key but does not remove it. Time complexity:
𝑂(1).
3. ExtractMax(): Returns the element with largest key and delete the element from the heap. Time complexity: 𝑂(log𝑛).
4. IncreaseKey(i, newKey): Increase the key of the ith element to 𝑛𝑒𝑤𝐾𝑒𝑦, and relocate it to maintain heap property. Time complexity: 𝑂(log𝑛).
5. DecreaseKey(i, newKey): Decrease the key of the ith element to 𝑛𝑒𝑤𝐾𝑒𝑦, and relocate it to maintain heap property. Time complexity: 𝑂(log𝑛).
6. Print(): Print the heap. Time complexity: 𝑂(𝑛).
You should write your program using features of object-oriented programming.
Input:
Create a menu for the six operations. Use 1 for insert, 2 for FindMax, 3 for ExtractMax, 4 for IncreaseKey, 5 for DecreaseKey, 6 for Print, and 7 for quit. Ask user to select an operation until option 7 is selected. Also prompt user for input any value which is required for the corresponding operations, i.e., insert, increaseKey, etc.
