Data structures & algorithms3 min

Heaps & Priority Queues

A Heap is a specialized tree-based data structure that satisfies the Heap Property. It is primarily used to implement Priority Queues, where elements are retrieved based on priority (e.g., smallest or largest) rather than the order they were inserted (FIFO).

Types of Heaps

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

[!WARNING] Unlike a Binary Search Tree (BST), there is no relationship between sibling nodes in a Heap! The left child is NOT necessarily smaller than the right child. The only guarantee is between Parent and Child.

Memory Layout (The Magic Array)

Heaps are conceptually structured as Complete Binary Trees (every level is fully filled, except possibly the bottom, which is filled from left to right). Because of this strict structure, Heaps are not built using Node objects and pointers!

Heaps are stored flatly inside a standard Array. We use math to find the children. If a parent is at index i:

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

This completely eliminates the memory overhead of left/right pointers and makes CPU caching incredibly fast.

Time Complexity

Operation	Time Complexity	Explanation
Find Min/Max	$O(1)$	It's always sitting right at index 0 of the array!
Insert	$O(\log N)$	Push to end of array, then "bubble up" (swap with parent) to restore heap property.
Extract Min/Max	$O(\log N)$	Swap root with last element, pop last element, then "bubble down" the new root.
Heapify	$O(N)$	Building a heap from an unsorted array takes linear time using Floyd's algorithm.

Implementation (Min-Heap Insert / Bubble Up)

typescript

class MinHeap {
  private heap: number[] = [];

  // Helper methods for math
  private getParentIdx(i: number) { return Math.floor((i - 1) / 2); }
  private swap(i: number, j: number) {
    const temp = this.heap[i];
    this.heap[i] = this.heap[j];
    this.heap[j] = temp;
  }

  // Insert O(log N)
  public insert(val: number): void {
    this.heap.push(val); // Put it at the very bottom
    this.bubbleUp(this.heap.length - 1); // Bubble it up to its correct spot
  }

  private bubbleUp(index: number): void {
    let currentIdx = index;
    let parentIdx = this.getParentIdx(currentIdx);
    
    // While we aren't the root, and we are SMALLER than our parent (violation)
    while (currentIdx > 0 && this.heap[currentIdx] < this.heap[parentIdx]) {
      this.swap(currentIdx, parentIdx);
      currentIdx = parentIdx;
      parentIdx = this.getParentIdx(currentIdx);
    }
  }
}

Real-World Applications

Dijkstra's Shortest Path Algorithm: Uses a Min-Heap to constantly extract the closest unvisited node.
Operating System Schedulers: Uses Priority Queues to decide which process gets CPU time next.
Top K Problems: The fastest way to find the "K Largest Elements" in a massive array is to push elements into a Min-Heap of size K. If the heap exceeds K, extract the minimum. What's left inside are the K largest!