Heaps in DSA: Priority Queues & Heap Algorithms

Master heap operations, heap sort, and priority queue implementations. This tutorial covers min/max heaps, heapify algorithms, and real-world applications with coding examples.

Heap Usage in Systems (2023)

Task Scheduling (45%)

Graph Algorithms (25%)

Memory Management (20%)

Other (10%)

1. Heap Fundamentals

Core Properties:

Complete Binary Tree: All levels filled except last, left-filled
Heap Property: Parent ≤ Children (Min-Heap) or Parent ≥ Children (Max-Heap)
Array Representation: Index relationships:
- Parent: (i-1)/2
- Left Child: 2i+1
- Right Child: 2i+2

Time Complexities:

Operation	Time	Space
Insert	O(log n)	O(1)
Extract Min/Max	O(log n)	O(1)
Heapify	O(n)	O(1)
Peek	O(1)	O(1)

Heap Implementation:


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

  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  extractMin() {
    if (this.isEmpty()) throw new Error("Heap is empty");
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return min;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = 
        [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  sinkDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }

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

    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = 
        [this.heap[smallest], this.heap[index]];
      this.sinkDown(smallest);
    }
  }
}

2. Heap Operations & Algorithms

Essential Algorithms:

Heap Sort


function heapSort(arr) {
  // Build max heap
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, arr.length, i);
  }

  // Extract elements one by one
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

Top K Elements


function topKElements(nums, k) {
  const minHeap = new MinHeap();
  
  for (const num of nums) {
    minHeap.insert(num);
    if (minHeap.size() > k) {
      minHeap.extractMin();
    }
  }
  
  return minHeap.heap;
}

// MinHeap needs size() method added:
size() {
  return this.heap.length;
}

Real-world Applications:

Priority Queues: Hospital triage systems
Dijkstra's Algorithm: Finding shortest paths
Merge K Sorted Lists: Efficient merging
Median Maintenance: Two-heap approach

3. Advanced Heap Techniques

Specialized Heaps:

Binomial Heap

Collection of binomial trees


class BinomialHeap {
  constructor() {
    this.trees = [];
    this.minNode = null;
  }

  merge(otherHeap) {
    this.trees = [...this.trees, ...otherHeap.trees];
    this.findMin();
  }
}

Fibonacci Heap

Optimal for decrease-key operations


class FibonacciHeap {
  constructor() {
    this.min = null;
    this.nodes = 0;
  }

  insert(key) {
    const node = new FibonacciNode(key);
    if (!this.min) {
      this.min = node;
    } else {
      // Merge with root list
      // Update min if needed
    }
    this.nodes++;
  }
}

Heap Optimization Techniques:

Decrease-Key: Critical for Dijkstra's algorithm
Bulk Insertion: O(n) heap construction
Lazy Deletion: Mark nodes instead of immediate removal
Memory Optimization: Pointer-based vs array-based

Heap Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Kth Largest Element	Min-heap of size K	O(n log k)
Merge K Sorted Arrays	Min-heap with pointers	O(n log k)
Sliding Window Median	Two heaps (min + max)	O(n log k)
Huffman Coding	Min-heap for tree construction	O(n log n)

4. Heap Variations & Applications

D-ary Heap

Generalization with d children per node


class DAryHeap {
  constructor(d = 2) {
    this.heap = [];
    this.d = d;
  }

  parent(i) {
    return Math.floor((i - 1) / this.d);
  }

  kthChild(i, k) {
    return this.d * i + k + 1;
  }
}

Min-Max Heap

Supports both min and max operations


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

  getMin() {
    return this.heap[0];
  }

  getMax() {
    if (this.heap.length <= 1) return this.heap[0];
    return Math.max(this.heap[1], this.heap[2] || -Infinity);
  }
}

Leftist Heap

Merge-friendly with null path length


class LeftistNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.npl = 0; // Null path length
  }
}

Heap Problem-Solving Checklist

✓ Choose min-heap vs max-heap based on problem

✓ Consider heap size for K-element problems

✓ Utilize heapify for O(n) construction

✓ Track additional node data when needed

DSA Expert Insight: Heap problems appear in 30% of technical interviews, especially in priority queue and top-K element scenarios. Mastering both basic operations and specialized heap variants is key to efficient problem-solving.

0 Interaction

0 Views

0 Likes