Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 6 Jun, 2021

Moderate

```
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'.
```

```
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.
```

```
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().
```

```
Print output of each query in a separate line.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

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.

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

- if element at ‘pos’ is larger than both its children