hardHeapPattern: Heap

Implement Max Priority Queue Solution

Problem Statement

Implement a `MaxPriorityQueue` class that supports the following operations for integer values: 1. `push(value)`: Inserts the given `value` into the priority queue. 2. `pop()`: Removes and returns the element with the highest priority (maximum value). If the priority queue is empty, it should return `-1`. 3. `peek()`: Returns the element with the highest priority without removing it. If the priority queue is empty, it should return `-1`. The internal data structure should efficiently maintain the max-heap property.

Examples

Example 1:

Input:Operations: `[["push", 10], ["push", 5], ["peek"], ["pop"], ["push", 20], ["peek"], ["pop"]]`

Output:`[null, null, 10, 10, null, 20, 20]`

Explanation: Initially, 10 and 5 are pushed. `peek` returns 10. `pop` removes 10. Then 20 is pushed. `peek` returns 20, and `pop` removes 20.

Example 2:

Input:Operations: `[["pop"], ["peek"], ["push", 7], ["peek"], ["pop"], ["pop"]]`

Output:`[-1, -1, null, 7, 7, -1]`

Explanation: Initial `pop` and `peek` on an empty queue return -1. After pushing 7, `peek` returns 7, and `pop` removes it. The final `pop` on an empty queue returns -1.

Constraints

`1 <= N <= 10^5` (N is the total number of operations)
`-10^9 <= value <= 10^9` (for `push` operations)
The `MaxPriorityQueue` will only contain integer values.
Operations `pop()` and `peek()` on an empty priority queue must return `-1`.

Time: O(logN) for push and pop, O(1) for peek Space: O(N)

The optimal approach uses a binary max-heap, typically implemented using an array or ArrayList. This structure efficiently maintains the max-heap property, ensuring that the maximum element is always at the root. Both `push` (inserting and then 'heapifying up') and `pop` (removing the root, replacing with the last element, and then 'heapifying down') operations take O(logN) time, while `peek` is O(1).

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 = []

    # Helper functions to get indices of parent and children
    def _getParentIndex(self, i):
        return (i - 1) // 2

    def _getLeftChildIndex(self, i):
        return 2 * i + 1

    def _getRightChildIndex(self, i):
        return 2 * i + 2

    # Helper functions to check existence of parent and children
    def _hasParent(self, i):
        return self._getParentIndex(i) >= 0

    def _hasLeftChild(self, i):
        return self._getLeftChildIndex(i) < len(self.heap)

    def _hasRightChild(self, i):
        return self._getRightChildIndex(i) < len(self.heap)

    # Helper functions to get parent and children values
    def _getParent(self, i):
        return self.heap[self._getParentIndex(i)]

    def _getLeftChild(self, i):
        return self.heap[self._getLeftChildIndex(i)]

    def _getRightChild(self, i):
        return self.heap[self._getRightChildIndex(i)]

    # Helper function to swap elements
    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    # Restores max-heap property by bubbling up the last element
    def _heapifyUp(self):
        index = len(self.heap) - 1
        while self._hasParent(index) and self._getParent(index) < self.heap[index]:
            self._swap(self._getParentIndex(index), index)
            index = self._getParentIndex(index)

    # Restores max-heap property by bubbling down the root element
    def _heapifyDown(self):
        index = 0
        while self._hasLeftChild(index):
            larger_child_index = self._getLeftChildIndex(index)
            # If right child exists and is larger, consider it
            if self._hasRightChild(index) and self._getRightChild(index) > self._getLeftChild(index):
                larger_child_index = self._getRightChildIndex(index)

            # If current element is already greater than or equal to its largest child,
            # max-heap property is satisfied.
            if self.heap[index] >= self.heap[larger_child_index]:
                break
            else:
                # Swap with the larger child and continue heapifying down
                self._swap(index, larger_child_index)
                index = larger_child_index

    """"""
    Inserts the given value into the priority queue.
    Time Complexity: O(log N) due to heapifyUp.
    :param value: The integer value to insert.
    """"""
    def push(self, value):
        self.heap.append(value)
        self._heapifyUp()

    """"""
    Removes and returns the element with the highest priority (maximum value).
    If the priority queue is empty, it returns -1.
    Time Complexity: O(log N) due to heapifyDown.
    :return: The maximum value or -1 if empty.
    """"""
    def pop(self):
        if len(self.heap) == 0:
            return -1
        if len(self.heap) == 1:
            return self.heap.pop()

        item = self.heap[0]  # The max element is always at the root
        self.heap[0] = self.heap.pop()  # Move the last element to the root
        self._heapifyDown()  # Restore heap property
        return item

    """"""
    Returns the element with the highest priority without removing it.
    If the priority queue is empty, it returns -1.
    Time Complexity: O(1).
    :return: The maximum value or -1 if empty.
    """"""
    def peek(self):
        if len(self.heap) == 0:
            return -1
        return self.heap[0]  # The max element is always at the root

# Driver code for reading from stdin and printing to stdout
pq = MaxPriorityQueue()
output = []

for line in sys.stdin:
    parts = line.strip().split()
    command = parts[0]

    if command == 'push':
        value = int(parts[1])
        pq.push(value)
    elif command == 'pop':
        output.append(str(pq.pop()))
    elif command == 'peek':
        output.append(str(pq.peek()))

sys.stdout.write("\n".join(output))
sys.stdout.write("\n") # Ensure a trailing newline