Heap & Priority Queue — Complete Step-by-Step Guide

Module 12 — Heap & Priority Queue: Always knowing the smallest or largest element instantly Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Heap Fundamentals & Array Memory Layout

A heap is a complete binary tree that maintains a strict heap-order property:

• Min-Heap: Every parent node is smaller than or equal to both of its children. The absolute minimum element in the entire data structure always resides at the root ($O(1)$ access).
• Max-Heap: Every parent node is greater than or equal to both of its children. The maximum element always sits at the root.

Because a heap is guaranteed to be a complete binary tree (every level is fully filled except possibly the last, which is filled strictly from left to right), it requires zero pointers. It is stored directly in a standard contiguous array.

Index Arithmetic Formulas (0-Indexed)

For any element located at array index $i$:

• Parent: floor((i - 1) / 2)
• Left Child: 2 * i + 1
• Right Child: 2 * i + 2

2. Core Operations: Sift-Up (Insert) & Sift-Down (Extract-Min)

Insertion (Heapify-Up / Sift-Up) — $O(log n)$

1. Place the new element at the very end of the array (maintaining the complete tree structure).
2. Compare the element with its parent.
3. If the element is smaller than its parent (in a min-heap), swap them.
4. Repeat upward until the heap property is satisfied or the root is reached.

void siftUp(vector<int>& heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] < heap[parent]) {
            swap(heap[i], heap[parent]);
            i = parent;
        } else {
            break;
        }
    }
}

Deletion / Extract-Min (Heapify-Down / Sift-Down) — $O(log n)$

1. Save the root element (this is your answer).
2. Move the last element of the array to the root position.
3. Delete the last element.
4. Compare the new root with its children and swap with the smaller child.
5. Repeat downward until both children are larger or a leaf is reached.

void siftDown(vector<int>& heap, int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

    if (smallest != i) {
        swap(heap[i], heap[smallest]);
        siftDown(heap, n, smallest);
    }
}

3. Why Build-Heap is $O(n)$, NOT $O(n log n)$

A common interview question asks why converting an unsorted array of size $n$ into a heap takes strictly $O(n)$ time rather than $O(n log n)$:

• If you insert $n$ elements one by one, each insertion can take $O(log n)$, giving $O(n log n)$.
• Build-Heap bottom-up (Floyd's Algorithm): Starts at the last non-leaf node (n/2 - 1) and calls siftDown backward to index 0.
• Most nodes reside near the bottom: $n/2$ nodes are leaves (height 0, 0 swaps), $n/4$ nodes have height 1 (at most 1 swap), $n/8$ have height 2.
• Mathematically: $sum_{h=0}^{log n} rac{n}{2^{h+1}} cdot h = n sum rac{h}{2^{h+1}} = O(n)$.

4. Priority Queue Applications & Standard Library

#include <queue>
#include <vector>

// 1. Max-Heap (Default in C++)
priority_queue<int> maxPQ;
maxPQ.push(10); maxPQ.push(30); maxPQ.push(20);
cout << maxPQ.top(); // Prints 30

// 2. Min-Heap
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(10); minPQ.push(30); minPQ.push(20);
cout << minPQ.top(); // Prints 10

// 3. Top K Frequent Elements Pattern (Keep heap of size K)
// Time Complexity: O(n log k), far superior to full sort O(n log n)