BackeasyHeap and Priority Queue Paytm

Max Priority Queue Operations Solution

Problem Statement

Implement a data structure, `MaxPriorityQueue`, that supports the following two operations: 1. `void insert(int val)`: Adds the element `val` to the priority queue. 2. `int extractMax()`: Removes and returns the element with the highest value from the priority queue. If the priority queue is empty, it should return -1. The element with the highest numerical value is considered to have the highest priority.

Example 1

Input

insert 30 insert 10 extractMax insert 20 extractMax

Output

30 20

Explanation: After inserting 30 and 10, extractMax returns 30. Then 20 is inserted, and the next extractMax returns 20.

Example 2

Input

extractMax insert 5 insert 15 extractMax extractMax extractMax

Output

-1 15 5 -1

Explanation: The first extractMax on an empty queue returns -1. After inserting 5 and 15, extractMax returns 15, then 5. The final extractMax on an empty queue returns -1.

Constraints

`1 <= number of operations <= 10^5`
`-10^9 <= val <= 10^9` for any `insert` operation.
The priority queue can contain duplicate values.
Each `insert` and `extractMax` operation should strive for an average time complexity of O(log N), where N is the current number of elements in the priority queue.

Max Priority Queue Operations Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Heap and Priority Queue Problems

Optimized Approach

Step-by-Step Dry Run

Tested Solutions