Module 10 : Heap & Priority Queue

A heap is a special tree-based data structure that allows fast access to the minimum or maximum element.
Whenever a problem says:

• “largest”
• “smallest”
• “top K”
• “most frequent”
• “next task”

Think HEAP immediately.

---

Min Heap & Max Heap

What is a Heap?

A heap is a complete binary tree that satisfies the heap property.

Types of Heap

Min Heap

• Parent ≤ children
• Root contains minimum element

Example:

        1
       / \
      3   5
     / \
    7   9

Max Heap

• Parent ≥ children
• Root contains maximum element

Example:

        9
       / \
      7   5
     / \
    3   1

---

Heap Representation

Heaps are usually implemented using arrays.

For index i:

• Left child → 2i + 1
• Right child → 2i + 2
• Parent → (i - 1) / 2

This avoids pointer overhead.

---

Heap Implementation (Concept)

Insert into Min Heap

Steps:

1. Insert element at end
2. Bubble up until heap property is restored

void insert(int x){
    heap[size] = x;
    int i = size;
    size++;

    while(i > 0 && heap[(i-1)/2] > heap[i]){
        swap(i, (i-1)/2);
        i = (i-1)/2;
    }
}

---

Remove Min (Extract)

Steps:

1. Replace root with last element
2. Heapify down

int extractMin(){
    int min = heap[0];
    heap[0] = heap[--size];
    heapify(0);
    return min;
}

---

Heapify

What is Heapify?

Heapify is the process of restoring heap property.

---

Heapify Down (Min Heap)

void heapify(int i){
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if(left < size && heap[left] < heap[smallest])
        smallest = left;
    if(right < size && heap[right] < heap[smallest])
        smallest = right;

    if(smallest != i){
        swap(i, smallest);
        heapify(smallest);
    }
}

Time complexity: O(log n)

---

Build Heap (Heapify All)

Convert array into heap in O(n) time.

for(int i = n/2 - 1; i >= 0; i--)
    heapify(i);

Important interview fact:

Building heap is O(n), not O(n log n)

---

Priority Queue

A Priority Queue is an abstract data structure where:

• Each element has a priority
• Highest (or lowest) priority element is served first

Internally implemented using heap.

---

Java Priority Queue

PriorityQueue<Integer> pq = new PriorityQueue<>(); // Min heap
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());

Operations:

• add → O(log n)
• poll → O(log n)
• peek → O(1)

---

K Largest / K Smallest Elements

Problem

Find K largest elements from an array.

---

Optimal Approach (Min Heap of Size K)

PriorityQueue<Integer> pq = new PriorityQueue<>();

for(int x : arr){
    pq.add(x);
    if(pq.size() > k)
        pq.poll();
}

Heap size never exceeds K
Time complexity: O(n log k)

---

Top K Frequent Elements

Problem

Find K elements with highest frequency.

Approach

1. Count frequency using HashMap
2. Use Min Heap on frequency

Map<Integer, Integer> map = new HashMap<>();
for(int x : nums)
    map.put(x, map.getOrDefault(x, 0) + 1);

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> a[1] - b[1]
);

for(int key : map.keySet()){
    pq.add(new int[]{key, map.get(key)});
    if(pq.size() > k)
        pq.poll();
}

---

Merge K Sorted Lists

Problem

Merge K sorted linked lists into one.

---

Approach

• Push first node of each list into Min Heap
• Always extract smallest node

PriorityQueue<ListNode> pq = new PriorityQueue<>(
    (a, b) -> a.val - b.val
);

for(ListNode head : lists)
    if(head != null)
        pq.add(head);

while(!pq.isEmpty()){
    ListNode node = pq.poll();
    curr.next = node;
    curr = curr.next;

    if(node.next != null)
        pq.add(node.next);
}

Time: O(n log k)

---

Heap vs Quickselect

Quickselect

• Based on partition (like quicksort)
• Average O(n)
• Worst-case O(n²)
• Not stable

---

Heap

• Guaranteed O(n log k)
• Uses extra space
• Better for streaming data

---

When to Use What?

Scenario	Use
Single query	Quickselect
Multiple queries	Heap
Streaming data	Heap
Worst-case safe	Heap

---

Scheduling Problems

Heaps are heavily used in scheduling.

---

Example: CPU Task Scheduling

Given tasks with deadlines and profit, maximize profit.

Approach:

• Sort tasks by deadline
• Use Min Heap on profit

for(Task t : tasks){
    pq.add(t.profit);
    if(pq.size() > t.deadline)
        pq.poll();
}

---

Meeting Rooms Problem

Find minimum meeting rooms required.

Approach:

• Sort by start time
• Min heap on end times

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(intervals[0].end);

for(int i = 1; i < n; i++){
    if(intervals[i].start >= pq.peek())
        pq.poll();
    pq.add(intervals[i].end);
}

---

Common Mistakes

• Forgetting heap size control
• Using max heap instead of min heap
• Sorting when heap is optimal
• Assuming heap is sorted (it is not)