Priority Queue (Binary Heap)

# Priority Queue (Binary Heap) ## Difficulty Medium ## Tags `heap`, `data structure`, `design` ## Problem Statement Implement a Max Priority Queue using a binary heap with the following operations: - `push(val)`: Insert element with the given value. - `pop()`: Remove and return the element with the highest value. - `peek()`: Return the element with the highest value without removing it. ## Constraints - -10⁴ ≤ val ≤ 10⁴ - At most 10⁴ operations. - `pop` and `peek` are called only when the heap is non-empty. ## Signatures ### Python ```python class MaxHeap: def push(self, val: int) -> None: pass def pop(self) -> int: pass def peek(self) -> int: pass ``` ### Java ```java public class MaxHeap { // Implement methods here } ``` ### Csharp ```csharp public class MaxHeap { // Implement methods here } ``` ### Cpp ```cpp class MaxHeap { public: // Implement methods here }; ``` ### C ```c void __init__() { } ``` ### Ruby ```ruby def __init__() end ``` ### Perl ```perl sub __init__ { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def __init__(): Unit = { } } ``` ### Haskell ```haskell __init__ :: ... -> ... __init__ args = undefined ``` ### Clojure ```clojure (defn __init__ [] ) ``` ### Scheme ```scheme (define (__init__ ) ) ``` ## Examples ### Example 1 **Input:** ``` heap = MaxHeap() heap.push(10) heap.push(20) heap.push(5) heap.peek() # returns 20 heap.pop() # returns 20 heap.peek() # returns 10 ``` ### Example 2 **Input:** ``` heap = MaxHeap() heap.push(1) heap.push(1) heap.push(1) heap.pop() # returns 1 heap.pop() # returns 1 ``` ## Hints ### Binary Heap Properties - Complete binary tree stored in an array. - For index i: parent = (i-1)//2, left child = 2*i+1, right child = 2*i+2. - Max-heap: parent ≥ children. ### Push (Sift Up) 1. Append element to end of array. 2. Compare with parent, swap if larger. 3. Repeat until heap property restored. ### Pop (Sift Down) 1. Swap root with last element. 2. Remove last element (the max). 3. Sift new root down: compare with children, swap with larger child if needed. 4. Repeat until heap property restored.