Heaps & Priority Queues — Complete Guide

What is a Heap?

A Heap is a specialized tree-based data structure that satisfies the Heap Property:

• Min-Heap: The value of each node is greater than or equal to the value of its parent. The minimum element is always at the root.
• Max-Heap: The value of each node is less than or equal to the value of its parent. The maximum element is always at the root.

       Min-Heap                  Max-Heap
          1                         10
        /   \                     /    \
       3     5                   8      9
      / \   /                   / \    /
     7   8 6                   4   2  5

A Heap is almost always implemented as a Complete Binary Tree stored inside a contiguous 1D Array.

Array Representation of Binary Heap

Because a heap is a complete binary tree, child and parent relationships can be calculated directly using zero-based array indices without storing explicit node pointers:

For any node at index i:

• Left Child Index: 2i + 1
• Right Child Index: 2i + 2
• Parent Index: Math.floor((i - 1) / 2)

Array: [1, 3, 5, 7, 8, 6]
Index:  0  1  2  3  4  5

Root (Index 0) = 1
Left Child of 1 (Index 0) = 2(0) + 1 = Index 1 (Value 3)
Right Child of 1 (Index 0) = 2(0) + 2 = Index 2 (Value 5)
Parent of 7 (Index 3) = floor((3-1)/2) = Index 1 (Value 3)

Core Operations & Time Complexities

Min-Heap Implementation in JavaScript

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(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

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

    insert(val) {
        this.heap.push(val);
        this._heapifyUp(this.heap.length - 1);
    }

    _heapifyUp(index) {
        let curr = index;
        while (curr > 0 && this.heap[curr] < this.heap[this.getParentIndex(curr)]) {
            const parent = this.getParentIndex(curr);
            this.swap(curr, parent);
            curr = parent;
        }
    }

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

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown(0);
        return min;
    }

    _heapifyDown(index) {
        let curr = index;
        const size = this.heap.length;

        while (this.getLeftChildIndex(curr) < size) {
            let smallest = this.getLeftChildIndex(curr);
            const right = this.getRightChildIndex(curr);

            if (right < size && this.heap[right] < this.heap[smallest]) {
                smallest = right;
            }

            if (this.heap[curr] <= this.heap[smallest]) break;

            this.swap(curr, smallest);
            curr = smallest;
        }
    }
}

Solved Problem 1: Kth Largest Element in an Array 🟡 Medium

Problem: Find the k-th largest element in an unsorted array.

Optimal Min-Heap Approach: Maintain a Min-Heap of size K. Iterate through the array: for each element, push to heap. If heap size exceeds k, pop the minimum. At the end, the root of the heap will be the k-th largest element!

javascript
function findKthLargest(nums, k) {
    const minHeap = new MinHeap(); // Assuming MinHeap implementation above

    for (const num of nums) {
        minHeap.insert(num);
        if (minHeap.heap.length > k) {
            minHeap.extractMin();
        }
    }

    return minHeap.peek();
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // Output: 5

Time: O(N log K) | Space: O(K)

Solved Problem 2: Merge K Sorted Lists 🔴 Hard

Problem: You are given an array of k linked-lists, each sorted in ascending order. Merge all the linked-lists into one sorted linked-list.

javascript
function mergeKLists(lists) {
    // Insert initial head nodes of all non-empty lists into a Min-Heap
    // Extract min, attach to result list, and push next node of extracted list
    // Time: O(N log K) where N is total nodes, K is number of lists
}

Frequently Asked Questions

Q: Why does buildHeap take O(N) time instead of O(N log N)?
A: Building a heap bottom-up processes nodes layer by layer. Most nodes reside near the bottom leaves where height is small (h=0, h=1). The total work is the summation of (N / 2^(h+1)) × O(h) which mathematically converges to O(N).

Q: When should I use a Priority Queue vs. Sorting?
A: If you have a static array and need full ordering, use Sorting O(N log N). If you have streaming/dynamic data or only need the top K elements, use a Priority Queue (Heap) O(N log K).