Implement a Max Heap

geeksforgeeks.org

Problem Statement

Implement a Max Heap supporting:

push(x)
pop()
peek()
size()

---

Intuition

A Max Heap always keeps:

Largest Element at Top

Java provides:

PriorityQueue

which is Min Heap by default.

To create Max Heap:

new PriorityQueue<>(
    Collections.reverseOrder()
);

---

Java Implementation

class maxHeap {

    PriorityQueue<Integer> pq;

    public maxHeap() {

        pq =
          new PriorityQueue<>(
              Collections.reverseOrder()
          );
    }

    public void push(int x) {
        pq.add(x);
    }

    public void pop() {
        pq.poll();
    }

    public int peek() {

        return pq.isEmpty()
               ? -1
               : pq.peek();
    }

    public int size() {
        return pq.size();
    }
}

---

Dry Run

push(10)

push(5)

push(20)

Heap:

20
10
5

peek()

Returns:

20

pop()

Removes:

20

New Top:

10

---

Complexity Analysis

Operation	Complexity
Push	O(log N)
Pop	O(log N)
Peek	O(1)
Size	O(1)

---

Interview One-Liner

A Max Heap maintains the largest element at the root, allowing efficient insertion and deletion in logarithmic time.

---

Pattern Learned

Kth Largest
Top K
Merge K Lists
Median Stream

=> Heap