easyHeap and Priority QueuePattern: Heap Operations

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.

Examples

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.

Time: O(log N) for both insert and extractMax operations Space: O(N) for storing N elements

The optimal approach utilizes a Max Heap, typically implemented using an array. `insert` involves adding the new element to the end of the array and then 'bubbling it up' (heapifying-up) to maintain the max-heap property, taking O(log N) time. `extractMax` involves swapping the root (max element) with the last element, removing the last element, and then 'bubbling down' (heapifying-down) the new root to restore the max-heap property, also taking O(log N) time.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import sys

class MaxPriorityQueue:
    def __init__(self):
        self.heap = []

    def _get_parent_index(self, i):
        return (i - 1) // 2
    
    def _get_left_child_index(self, i):
        return 2 * i + 1
    
    def _get_right_child_index(self, i):
        return 2 * i + 2

    def _has_parent(self, i):
        return self._get_parent_index(i) >= 0
    
    def _has_left_child(self, i):
        return self._get_left_child_index(i) < len(self.heap)
    
    def _has_right_child(self, i):
        return self._get_right_child_index(i) < len(self.heap)

    def _get_parent(self, i):
        return self.heap[self._get_parent_index(i)]
    
    def _get_left_child(self, i):
        return self.heap[self._get_left_child_index(i)]
    
    def _get_right_child(self, i):
        return self.heap[self._get_right_child_index(i)]

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert(self, val):
        self.heap.append(val)
        self._heapify_up()

    def extract_max(self):
        if not self.heap:
            return -1

        if len(self.heap) == 1:
            return self.heap.pop()

        item = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down()
        return item

    def _heapify_up(self):
        index = len(self.heap) - 1
        while self._has_parent(index) and self._get_parent(index) < self.heap[index]:
            self._swap(index, self._get_parent_index(index))
            index = self._get_parent_index(index)

    def _heapify_down(self):
        index = 0
        while self._has_left_child(index):
            larger_child_index = self._get_left_child_index(index)
            if self._has_right_child(index) and self._get_right_child(index) > self._get_left_child(index):
                larger_child_index = self._get_right_child_index(index)

            if self.heap[index] > self.heap[larger_child_index]:
                break
            else:
                self._swap(index, larger_child_index)
                index = larger_child_index

if __name__ == "__main__":
    num_operations = int(sys.stdin.readline())
    pq = MaxPriorityQueue()
    results = []

    for _ in range(num_operations):
        line = sys.stdin.readline().split()
        operation = line[0]

        if operation == "insert":
            val = int(line[1])
            pq.insert(val)
        elif operation == "extractMax":
            results.append(str(pq.extract_max()))
    
    sys.stdout.write("\n".join(results) + "\n")