Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 6 Jun, 2021

Implement a priority queue

Moderate
Asked in companies
AmazonOracleOYO

Problem statement

You have to implement the pop function of Max Priority Queue and implement using a heap.


Functions :
a) push(int x) : 'x' has to be inserted in the priority queue. This has been implemented already

b) pop() : return the maximum element in the priority queue, if priority queue is empty then return '-1'.


Example:
We perform the following operations on an empty priority queue:

When operation push(5) is performed, we insert 1 in the priority queue.

When operation push(2) is performed, we insert 2 in the priority queue. 

When operation pop() is performed, we remove the maximum element from the priority queue and print which is 5.

When operation push(3) is performed, we insert 1 in the priority queue.

When operation pop() is performed, we remove the maximum element from the priority queue and print which is 3.
Input Format:
The first line of contains a single integer, ‘n’ , representing the  number of operations.

The next ‘n’ lines of each test case contain operations that have to be performed on the stack. 

Operations of the format
1 x : denotes to perform the operation push(x).
2 : denotes to perform the operation pop(). 
Output Format :
Print output of each query in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function. 

Approaches

01 Approach

Approach:
The main idea is to remove the element at the peak. As its empty we replace it by the element at the end of the heap(bottommost element). Now to maintain the heap property that the element is larger that both its children, we continuously move the element replacing it with the greater child.

 

Algorithm:

  • Save the element in the peak of heap
  • remove the last element and place it at the peak
  • assign the position of this element to a variable say ‘pos’ which is 0
  • run a loop indefinitely
    • if element  at ‘pos’ is larger than both its children
      • break the loop
    • else replace it with the larger child and assign ‘pos’ with the position it replaced to.