Master Heaps & Priority Queues — Complete Guide

1. Introduction to Heaps

A Heap is a specialized, tree-based data structure that satisfies the Heap Property. Unlike a Binary Search Tree (BST), which maintains a global left-to-right sorted order, a Heap maintains a parent-to-child relative ordering:

• Min-Heap: The key at the root node is the minimum element in the entire tree. For every node v, value(parent(v)) ≤ value(v).
• Max-Heap: The key at the root node is the maximum element in the entire tree. For every node v, value(parent(v)) ≥ value(v).

+─────────────────────────────────────────────────────────────────────────────+
|                        MIN-HEAP VS MAX-HEAP STRUCTURE                       |
+─────────────────────────────────────────────────────────────────────────────+

         MIN-HEAP (Root = Min)                      MAX-HEAP (Root = Max)
                 [ 2 ]                                      [ 90 ]
               /       \                                  /        \
            [ 5 ]     [ 8 ]                            [ 80 ]     [ 75 ]
           /    \     /                                /    \     /
        [ 12 ] [ 9 ] [ 15 ]                         [ 50 ] [ 60 ] [ 40 ]

A Binary Heap is always structured as a Complete Binary Tree—meaning every tree level is completely filled, except possibly the bottom level, which is filled sequentially from left to right with no gaps.

2. Why Learn Heaps?

A Heap is the underlying engine for Priority Queues, a fundamental abstract data type used across operating systems, network protocols, and graph algorithms.

Real-World Engineering Analogy: The Emergency Room Triage

In a standard FIFO queue (like a movie ticket counter), people are served strictly in the order they arrive. In an Emergency Room, patients are processed by medical severity (priority), not arrival time. A critical patient who arrives at 10:05 PM is treated before a non-urgent patient who arrived at 9:00 PM. A Priority Queue backed by a Max-Heap allows the hospital system to extract the highest-priority patient in instant O(1) lookup and O(log N) extraction.

Where Heaps Power Industry Systems:

1. Operating System Schedulers: Linux CFS (Completely Fair Scheduler) and CPU thread schedulers use priority heaps to dispatch compute tasks based on priority and nice values.
2. Dijkstra’s Shortest Path & Prim’s Minimum Spanning Tree: Graph algorithms rely on min-heaps to select the next nearest vertex in O(E log V) time.
3. Bandwidth & Packet Throttling: Network routers use priority queues to prioritize time-sensitive VOIP/video packets over background file downloads.
4. Real-time Analytics: Tracking rolling Top-K metrics (e.g., top trending search queries on Google or Twitter).
5. Data Stream Processing: Computing streaming percentiles and dynamic medians.

3. Array Representation of a Binary Heap

Because a Binary Heap is strictly a Complete Binary Tree, we do not need to allocate heap nodes with expensive left/right memory pointers. Instead, the tree is stored inside a contiguous 1D Array.

+─────────────────────────────────────────────────────────────────────────────+
|                      ARRAY INDEXING MATHEMATICAL FORMULAS                   |
+─────────────────────────────────────────────────────────────────────────────+

 Tree Structure:
                     Index 0 [ 2 ]
                   /               \
         Index 1 [ 5 ]           Index 2 [ 8 ]
        /             \         /
  Index 3 [ 12 ] Index 4 [ 9 ] Index 5 [ 15 ]

 Array Layout:
  Index:   [ 0 ]   [ 1 ]   [ 2 ]   [ 3 ]   [ 4 ]   [ 5 ]
  Value:     2       5       8      12       9      15

Zero-Based Index Navigation Formulas:

For any element residing at index i:

• Parent Index: lfloor (i - 1 / 2) rfloor
• Left Child Index: 2i + 1
• Right Child Index: 2i + 2
• Is Leaf Node?: i ≥ lfloor (N / 2) rfloor, where N is total element count.

4. Core Heap Operations & Algorithms

1. Insertion (insert / push) — O(log N)

When a new element is added:

1. Append the new value to the end of the array (maintaining the Complete Binary Tree shape).
2. Heapify Up (Bubble Up): Compare the element with its parent. If the heap invariant is violated (e.g. child < parent in a Min-Heap), swap them. Repeat until the element reaches its valid position or becomes the root.

Inserting value [ 1 ] into Min-Heap [2, 5, 8, 12, 9, 15]:
Step 1: Append at index 6 -> [2, 5, 8, 12, 9, 15, 1]
Step 2: Compare with parent at index 2 (val 8). 1 < 8 -> Swap! -> [2, 5, 1, 12, 9, 15, 8]
Step 3: Compare with parent at index 0 (val 2). 1 < 2 -> Swap! -> [1, 5, 2, 12, 9, 15, 8]
Result: Valid Min-Heap restored in O(log N) height swaps.

2. Extraction (extractMin / pop) — O(log N)

When removing the highest-priority root element:

1. Save the root element at index 0 to return.
2. Move the last element of the array to index 0 and shrink the array size by 1.
3. Heapify Down (Sift Down): Compare the new root with its children. Swap with the smaller child (in Min-Heap) or larger child (in Max-Heap). Repeat downward until the invariant is restored.

Extracting Min from [1, 5, 2, 12, 9, 15, 8]:
Step 1: Save root (1). Move last element (8) to index 0 -> [8, 5, 2, 12, 9, 15]
Step 2: Compare 8 with children (5 and 2). Smallest child is 2 -> Swap! -> [2, 5, 8, 12, 9, 15]
Result: Valid Min-Heap restored with new root 2.

3. Building a Heap in Linear Time (buildHeap) — O(N) Proof

Given an arbitrary unsorted array of N numbers, we can transform it into a valid heap by running heapifyDown on all non-leaf nodes starting from index lfloor (N / 2) rfloor - 1 down to index 0.

Why is buildHeap O(N) and not O(N log N)?
- Nodes at height 0 (leaves, N/2 nodes) require 0 sift-down steps.
- Nodes at height 1 (N/4 nodes) require at most 1 sift-down step.
- Nodes at height 2 (N/8 nodes) require at most 2 sift-down steps.
- The root at height h = log N requires at most h steps.

Total Operations S = sum_{h=0}^{log N} (N / 2^(h+1)) * h
S = (N/2) * [ (1/2) + (2/4) + (3/8) + (4/16) + ... ]
The summation series evaluates to exactly 2.
Therefore: S = (N/2) * 2 = O(N) linear time!

5. Heap Sort Algorithm

Heap Sort is an in-place, comparison-based sorting algorithm that guarantees O(N log N) worst-case time complexity with O(1) auxiliary space.

+─────────────────────────────────────────────────────────────────────────────+
|                            HEAP SORT WORKFLOW                               |
+─────────────────────────────────────────────────────────────────────────────+

 Input Array: [ 4, 10, 3, 5, 1 ]

 Phase 1: Build Max-Heap in-place -> [ 10, 5, 3, 4, 1 ] (O(N) time)

 Phase 2: Repeatedly swap root with last unsorted element and heapifyDown:
   Swap 10 with 1 -> [ 1, 5, 3, 4 | 10 ] -> Heapify down -> [ 5, 4, 3, 1 | 10 ]
   Swap 5 with 1  -> [ 1, 4, 3 | 5, 10 ] -> Heapify down -> [ 4, 1, 3 | 5, 10 ]
   Swap 4 with 3  -> [ 3, 1 | 4, 5, 10 ] -> Heapify down -> [ 3, 1 | 4, 5, 10 ]
   Swap 3 with 1  -> [ 1 | 3, 4, 5, 10 ]

 Final Sorted Array: [ 1, 3, 4, 5, 10 ]

6. Multi-Language Implementations & Syntax

C++ (std::priority_queue)

cpp
#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 1. Max-Heap (Default in C++)
    std::priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);
    std::cout << "Max-Heap Top: " << maxHeap.top() << "\n"; // Outputs 30

    // 2. Min-Heap in C++
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);
    std::cout << "Min-Heap Top: " << minHeap.top() << "\n"; // Outputs 10

    return 0;
}

Java (java.util.PriorityQueue)

java
import java.util.Collections;
import java.util.PriorityQueue;

public class HeapDemo {
    public static void main(String[] args) {
        // 1. Min-Heap (Default in Java)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(40);
        minHeap.offer(10);
        minHeap.offer(25);
        System.out.println("Min element: " + minHeap.poll()); // 10

        // 2. Max-Heap in Java using Custom Comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(40);
        maxHeap.offer(10);
        maxHeap.offer(25);
        System.out.println("Max element: " + maxHeap.poll()); // 40
    }
}

Python (heapq)

python
import heapq

# 1. Min-Heap (Default in Python)
data = [40, 10, 25, 5, 90]
heapq.heapify(data) # In-place O(N) buildHeap
print("Min element:", heapq.heappop(data)) # 5

# Push new element
heapq.heappush(data, 15)

# 2. Max-Heap in Python (Negate values)
max_heap = []
for val in [40, 10, 25, 5, 90]:
    heapq.heappush(max_heap, -val)

print("Max element:", -heapq.heappop(max_heap)) # 90

JavaScript Custom MinHeap Class

javascript
class MinHeap {
    constructor() {
        this.heap = [];
    }

    getParentIndex(i) { return Math.floor((i - 1) / 2); }
    getLeftChildIndex(i) { return 2 * i + 1; }
    getRightChildIndex(i) { return 2 * i + 2; }

    swap(i1, i2) {
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }

    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }

    push(val) {
        this.heap.push(val);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIdx = this.getParentIndex(index);
            if (this.heap[parentIdx] > this.heap[index]) {
                this.swap(parentIdx, index);
                index = parentIdx;
            } else {
                break;
            }
        }
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const root = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return root;
    }

    heapifyDown() {
        let index = 0;
        const length = this.heap.length;

        while (this.getLeftChildIndex(index) < length) {
            let smallerChildIdx = this.getLeftChildIndex(index);
            let rightChildIdx = this.getRightChildIndex(index);

            if (rightChildIdx < length && this.heap[rightChildIdx] < this.heap[smallerChildIdx]) {
                smallerChildIdx = rightChildIdx;
            }

            if (this.heap[index] > this.heap[smallerChildIdx]) {
                this.swap(index, smallerChildIdx);
                index = smallerChildIdx;
            } else {
                break;
            }
        }
    }

    size() { return this.heap.length; }
}

7. Time & Space Complexity Summary

8. Classic Interview Problems with Solutions

Problem 1: Kth Largest Element in an Array (Top-K Pattern)

Problem Statement: Given an integer array nums and an integer k, return the k^{th} largest element in the array without full O(N log N) sorting.

Step-by-Step Logic:

1. Maintain a Min-Heap of size bounded to exactly k.
2. Iterate through every number in nums:
   • Push number into the Min-Heap.
   • If heap size exceeds k, pop the minimum element.
3. After scanning all N elements, the Min-Heap holds the k largest elements, with the k^{th} largest sitting at the root!

python
import heapq

def findKthLargest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
            
    return min_heap[0]

• Time Complexity: O(N log K) — Significantly faster than O(N log N) when K ll N.
• Space Complexity: O(K) — Auxiliary heap storage.

Problem 2: Find Median from Data Stream (Two-Heaps Pattern)

Problem Statement: Design a data structure that supports adding numbers from a data stream and calculating the dynamic median in O(1) time.

Step-by-Step Logic:

Divide numbers into two halves:

1. Max-Heap (leftHeap): Stores the smaller half of all numbers.
2. Min-Heap (rightHeap): Stores the larger half of all numbers.
3. Invariant: leftHeap size is either equal to rightHeap or has exactly 1 more element.
4. Finding Median:
   • If total elements is odd: median is leftHeap.top().
   • If total elements is even: median is (leftHeap.top() + rightHeap.top()) / 2.0.

cpp
#include <queue>
#include <vector>

class MedianFinder {
private:
    std::priority_queue<int> maxHeap; // Small half
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // Large half

public:
    void addNum(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        // Rebalance heaps so size difference is at most 1
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

• Time Complexity: addNum: O(log N), findMedian: O(1).
• Space Complexity: O(N) total storage.

9. Common Pitfalls & Interview Traps

1. Confusing Min-Heap with Max-Heap Defaults: Remember that C++ std::priority_queue defaults to a Max-Heap, whereas Java PriorityQueue and Python heapq default to a Min-Heap.
2. Assuming Heaps are Fully Sorted: A heap only guarantees parent-child ordering. Level-by-level inspection will not yield elements in sorted order.
3. Searching in a Heap is O(N): Finding an arbitrary element inside a heap requires linear scanning because left vs right children are not ordered relative to each other.
4. Inefficient BuildHeap: Calling insert() N times costs O(N log N), whereas bottom-up buildHeap() costs only O(N).

10. Frequently Asked Questions (FAQ)

Q1: When should I use a Heap instead of sorting?

A: Use a Heap when you need to maintain continuous access to extremal values (min/max) from a dynamic stream of elements, or when solving Top-K problems where K ll N. A heap achieves O(N log K) instead of O(N log N) sorting.

Q2: Why is a Binary Heap implemented using an Array instead of pointers?

A: Because a Binary Heap is a complete binary tree with no internal missing nodes, array indices mathematically represent parent-child links. Arrays provide zero pointer memory overhead and take full advantage of CPU cache prefetching.

Q3: How do you implement a Max-Heap in Python since heapq only supports Min-Heap?

A: Multiply all inserted values by -1. When extracting via heappop(), multiply the returned value by -1 again to restore the original number. Alternatively, wrap items inside a tuple with a negated priority key.

Q4: Can a Binary Heap contain duplicate elements?

A: Yes. Duplicate values satisfy the heap invariant (≥ or ≤) and are placed in adjacent branches or child levels without issue.

Q5: What is the difference between a Binary Heap and a Fibonacci Heap?

A: A Binary Heap provides O(log N) insertion and extraction. A Fibonacci Heap provides theoretical O(1) amortized insertion and decrease-key operations, making it valuable for dense graph algorithms, though its high constant factors make Binary Heaps faster in practice.

Q6: What is the space complexity of Heap Sort?

A: Heap Sort runs in strictly O(1) auxiliary space because the input array is converted into a heap in-place and sorted without allocating extra arrays.