Implement a priority queue

Moderate
0/80
profile
Contributed by
42 upvotes
Asked in companies
SalesforceMorgan StanleySamsung

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
8
1 4
1 9
2 
1 5
2 
1 10
1 1
2
Sample Output 1 :
9
5
10
Explanation For Sample Output 1 :
After processing 1 4
The elements in the priority queue are 4

After processing 1 9
The elements in the priority queue are 4,9

After processing 2
The largest element which is 9 is printed and removed from the queue
The elements in the priority queue are 4

After processing 1 5
The elements in the priority queue are 4,5

After processing 2
The largest element which is 5 is printed and removed from the queue

After processing 1 10
The elements in the priority queue are 4,10

After processing 1 1
The elements in the priority queue are 1,4,10

After processing 2
The largest element which is 10 is printed and removed from the queue
The elements in the priority queue are 1,4
Sample Input 2 :
8
2 
1 6
2 
2 
2 
1 2
1 9
1 5
Sample Output 2 :
-1
6
-1
-1
Constraints :
1 <= n <= 10^6

Time Limit: 1 sec
Hint

Use the concept of max heap.

Approaches (1)
Array representation of heap

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.
Time Complexity

O(log(n)) where ‘n’ is the size of the heap
 

We traverse the heap level wise and as there are log(n) levels in a binary heap the Time Complexity is O(log(n)).

Space Complexity

O(1)

 

We are not using any extra space in any operation.

Code Solution
(100% EXP penalty)
Implement a priority queue
Full screen
Console