Day 8: Heaps & Priority Queues

What You'll Learn Today

• The heap concept and its properties
• Min heap and max heap implementations
• How priority queues work
• Heap sort implementation

---

What Is a Heap?

A heap is a complete binary tree where parent nodes maintain a specific ordering relationship with their children.

flowchart TB
    subgraph MinHeap["Min Heap (parent ≤ child)"]
        M1["1"] --> M2["3"]
        M1 --> M3["2"]
        M2 --> M4["7"]
        M2 --> M5["6"]
        M3 --> M6["5"]
        M3 --> M7["4"]
    end
    subgraph MaxHeap["Max Heap (parent ≥ child)"]
        X7["7"] --> X5["5"]
        X7 --> X6["6"]
        X5 --> X1["1"]
        X5 --> X3["3"]
        X6 --> X2["2"]
        X6 --> X4["4"]
    end
    style MinHeap fill:#3b82f6,color:#fff
    style MaxHeap fill:#8b5cf6,color:#fff

Heap Properties

1. Complete binary tree: Every level is fully filled except possibly the last
2. Heap condition: Min heap: parent ≤ child; Max heap: parent ≥ child

---

Array Representation

Heaps are efficiently stored as arrays.

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

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

---

Min Heap Implementation

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

  _parentIndex(i) { return Math.floor((i - 1) / 2); }
  _leftChildIndex(i) { return 2 * i + 1; }
  _rightChildIndex(i) { return 2 * i + 2; }
  _swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

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

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

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

  _bubbleUp(index) {
    while (index > 0) {
      const parent = this._parentIndex(index);
      if (this.heap[parent] <= this.heap[index]) break;
      this._swap(parent, index);
      index = parent;
    }
  }

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

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

  _bubbleDown(index) {
    const length = this.heap.length;
    while (true) {
      let smallest = index;
      const left = this._leftChildIndex(index);
      const right = this._rightChildIndex(index);

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

      this._swap(index, smallest);
      index = smallest;
    }
  }
}

const heap = new MinHeap();
[5, 3, 8, 1, 2, 7].forEach(v => heap.insert(v));
console.log(heap.peek());       // 1
console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 2
console.log(heap.extractMin()); // 3

---

Heap Operation Flow

Insert (Bubble Up)

flowchart TB
    subgraph Before["Before Insert"]
        B1["1"] --> B3["3"]
        B1 --> B5["5"]
        B3 --> B7["7"]
        B3 --> B6["6"]
    end
    subgraph After["After Inserting 2"]
        A1["1"] --> A2["2"]
        A1 --> A5["5"]
        A2 --> A7["7"]
        A2 --> A6["6"]
        A5 --> A3["3"]
    end
    style Before fill:#3b82f6,color:#fff
    style After fill:#22c55e,color:#fff

Extract Min (Bubble Down)

flowchart TB
    subgraph Before["Before Extract"]
        B1["1"] --> B3["3"]
        B1 --> B5["5"]
        B3 --> B7["7"]
    end
    subgraph After["After Extracting 1"]
        A3["3"] --> A7["7"]
        A3 --> A5["5"]
    end
    style Before fill:#3b82f6,color:#fff
    style After fill:#22c55e,color:#fff

---

Priority Queue

A priority queue dequeues elements by priority rather than insertion order. It is typically implemented with a heap.

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

  _parentIndex(i) { return Math.floor((i - 1) / 2); }
  _leftChildIndex(i) { return 2 * i + 1; }
  _rightChildIndex(i) { return 2 * i + 2; }
  _swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this._bubbleUp(this.heap.length - 1);
  }

  _bubbleUp(index) {
    while (index > 0) {
      const parent = this._parentIndex(index);
      if (this.heap[parent].priority <= this.heap[index].priority) break;
      this._swap(parent, index);
      index = parent;
    }
  }

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

    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._bubbleDown(0);
    return top;
  }

  _bubbleDown(index) {
    const length = this.heap.length;
    while (true) {
      let smallest = index;
      const left = this._leftChildIndex(index);
      const right = this._rightChildIndex(index);

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

      this._swap(index, smallest);
      index = smallest;
    }
  }

  get size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
}

const pq = new PriorityQueue();
pq.enqueue("Low priority task", 5);
pq.enqueue("Critical bug fix", 1);
pq.enqueue("Feature request", 3);
pq.enqueue("Urgent issue", 2);

while (!pq.isEmpty()) {
  const item = pq.dequeue();
  console.log(`[Priority ${item.priority}] ${item.value}`);
}
// [Priority 1] Critical bug fix
// [Priority 2] Urgent issue
// [Priority 3] Feature request
// [Priority 5] Low priority task

---

Heap Sort

A sorting algorithm powered by heaps.

function heapSort(arr) {
  const n = arr.length;

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

  // Extract elements one by one
  for (let i = n - 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);
  }
}

console.log(heapSort([12, 11, 13, 5, 6, 7]));
// [5, 6, 7, 11, 12, 13]

Property	Value
Time	O(n log n)
Space	O(1) (in-place)
Stable	No

---

Practical Example: K Largest Elements

function kLargest(arr, k) {
  const minHeap = new MinHeap();

  for (const num of arr) {
    minHeap.insert(num);
    if (minHeap.size > k) {
      minHeap.extractMin();
    }
  }

  const result = [];
  while (minHeap.size > 0) {
    result.push(minHeap.extractMin());
  }
  return result;
}

console.log(kLargest([3, 1, 5, 12, 2, 11], 3)); // [5, 11, 12]

---

Heap Time Complexities

Operation	Complexity
Insert	O(log n)
Peek (min/max)	O(1)
Extract (min/max)	O(log n)
Build heap	O(n)
Heap sort	O(n log n)

---

Summary

Concept	Description
Heap	Complete binary tree with ordering between parent and child
Min Heap	Parent ≤ child; root is the minimum
Max Heap	Parent ≥ child; root is the maximum
Priority Queue	Dequeues elements by priority
Heap Sort	In-place O(n log n) sort using a heap

Key Takeaways

1. Heaps are efficiently stored as arrays
2. Insert and extract are O(log n); peek is O(1)
3. Priority queues are commonly implemented with heaps
4. Heap sort is in-place O(n log n) but unstable

---

Practice Problems

Problem 1: Basic

Implement a max heap (reverse the comparison in MinHeap).

Problem 2: Intermediate

Implement a system to find the running median of a data stream using two heaps (a max heap and a min heap).

Challenge

Merge K sorted arrays into a single sorted array using a priority queue.

---

References

• Wikipedia - Heap
• Visualgo - Heap
• Wikipedia - Heapsort

---

Next up: In Day 9, we'll explore "Graphs" — a powerful data structure for representing relationships between nodes.