Heap: The Emergency Room

Prologue: "I came first!"

Scene at hospital ER:

Patient A (cold, arrived 9am): "I came first! Why not me?" Nurse: "That person is heart attack patient, must go first." Patient B (heart attack, 10am): (straight to stretcher)

Me: "Not first-come-first-served?"

Bank number tickets are FIFO (First In First Out), but ER is different. Heart attack patient gets treated before cold patient, even if they arrived later. Seeing this, I understood: "Oh, some systems aren't first-come-first-served."

Why I Studied This

At work, got "task scheduler" assignment.

Requirements:

• Urgent tasks execute immediately
• Normal tasks wait
• Process by priority

Me: "Put in array, sort?"

Senior: "Sort every time? O(n log n)? Slow. Use Heap."

Started studying heaps.

Writing code, I realized task priority management was key. Every time user clicks button, new task arrives. Urgent tasks (server down, payment error) must execute before normal tasks (log cleanup, stats generation). Initially I put tasks in array and called sort() every time. But as tasks grew to 1000, 10000, it got slow.

Senior developer commented in code review: "Heap is O(log n), why do O(n log n) sort every time?"

What Confused Me

• Heap is tree?
• Why must parent > child?
• Is O(1) max finding that great?
• Min Heap vs Max Heap difference?

Most importantly: "How different from Queue?"

Queue also inserts and removes data, heap also inserts and removes. Why bother with tree structure? Didn't click. Plus "complete binary tree" term was unfamiliar, and representing tree as array wasn't intuitive.

Another confusing thing was "Memory Heap vs Data Structure Heap". In C/C++ dynamic memory allocation, we say "heap area", but it's completely different from data structure heap despite same name. Memory heap is just empty space chunk, data structure heap is tree for priority management. Initially confused these two.

The Aha Moment: "ER vs Bank"

Senior's analogy:

Regular Queue (Bank): "First-come-first-served. Order matters."

Priority Queue (ER): "Critical first. Heart attack beats cold, regardless of arrival time."

Heap: "Most efficient data structure for Priority Queue. Top (Root) always has most important item."

"Oh, importance order!"

Bank only cares who came first (time), but ER cares who's more critical (priority). Heap was the tool for efficient "priority management". And Root always has max value (Max Heap) or min value (Min Heap), so it embodies the philosophy: "Just find the most important one quickly."

1. Heap Structure: Complete Binary Tree

Max Heap

Rule: Parent ≥ Child

      100  ← Max (Root)
     /   \
   50     80
  / \    / \
 30  40 60  70

Properties:

• Root = maximum
• Parent > child (always)
• Left/right child order doesn't matter

For example, you can swap positions of 50 and 80. What matters is 100 at Root.

Min Heap

Rule: Parent ≤ Child

       5  ← Min
      / \
    10  15
   / \
  20  30

Min Heap has minimum at Root. Dijkstra shortest path algorithm uses Min Heap to find "nearest node".

What is Complete Binary Tree?

"Complete Binary Tree" = Tree filled from left with no gaps

     O
    / \
   O   O
  / \
 O   O  ← Filled in this order

I understood this as "apartment move-in". When moving into apartments, you fill from unit 101 in order, not skip middle units and start from 1001, right? Heap is same. Fill array from index 0 in order.

2. Array Implementation

Heap is complete binary tree → can represent as array!

// Max Heap
const heap = [100, 50, 80, 30, 40, 60, 70];

// Index relationships
// parent(i) = Math.floor((i-1)/2)
// left(i) = 2*i + 1
// right(i) = 2*i + 2

Index:  0   1   2   3   4   5   6
Value: 100  50  80  30  40  60  70

Tree form:
      100 (0)
     /      \
   50(1)    80(2)
   / \      / \
 30(3) 40(4) 60(5) 70(6)

I found this fascinating initially. "Tree but represented as array?" But complete binary tree has no gaps, so has 1:1 correspondence with array indices. Can express parent-child relationship as formula, so can build tree without pointers.

For example, index 2 (value 80)'s left child is 2*2+1 = 5 (value 60), right child is 2*2+2 = 6 (value 70). Parent is (2-1)/2 = 0 (value 100). Express tree structure just by calculation.

3. Insert: O(log n)

Process

1. Add at end
2. Compare with parent
3. If larger, Swap (Bubble Up)
4. Repeat

I compared this to "new employee promotion". New hire starts at bottom (entry level). But if performance is good, moves up. If better than parent (boss), swap positions. Keep moving up until can't go higher, then settle.

Code

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

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

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

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

const heap = new MaxHeap();
heap.insert(100);
heap.insert(50);
heap.insert(150);  // 150 bubbles to Root!
console.log(heap.heap);  // [150, 50, 100]

Inserting 150:

1. Add at end: [100, 50, 150]
2. Compare with parent (100) → 150 > 100 → Swap
3. Final: [150, 50, 100]

This is O(log n) because only need to go up tree height. Complete binary tree height is log n.

4. Extract Max: O(log n)

Process

1. Remove Root (max)
2. Move last element to Root
3. Compare with children
4. If smaller, Swap (Bubble Down)
5. Repeat

I compared this to "CEO resignation and promotion". When CEO (Root) resigns, put youngest (last element) in CEO position. Obviously lacks ability, so swap with more capable subordinate (child). Keep going down until settle at appropriate position.

Code

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

    const max = this.heap[0];
    this.heap[0] = this.heap.pop();  // Last to Root
    this.bubbleDown(0);

    return max;
  }

  bubbleDown(index) {
    while (true) {
      const leftIndex = 2 * index + 1;
      const rightIndex = 2 * index + 2;
      let largest = index;

      if (leftIndex < this.heap.length &&
          this.heap[leftIndex] > this.heap[largest]) {
        largest = leftIndex;
      }

      if (rightIndex < this.heap.length &&
          this.heap[rightIndex] > this.heap[largest]) {
        largest = rightIndex;
      }

      if (largest === index) break;

      [this.heap[index], this.heap[largest]] =
      [this.heap[largest], this.heap[index]];

      index = largest;
    }
  }
}

const max = heap.extractMax();
console.log(max);  // 150

5. Heapify: Turn Array into Heap O(n)

"Turn existing array into heap?"

class MaxHeap {
  heapify(arr) {
    this.heap = arr;

    // From last parent node, bubbleDown backwards
    const lastParent = Math.floor((this.heap.length - 2) / 2);
    for (let i = lastParent; i >= 0; i--) {
      this.bubbleDown(i);
    }
  }
}

const heap = new MaxHeap();
heap.heapify([30, 50, 20, 100, 10]);
console.log(heap.heap);  // [100, 50, 20, 30, 10]

I initially doubted: "Inserting one by one is O(n log n), but heapify is O(n)?" But looking at proof, leaf nodes (half) already satisfy heap condition so no work needed, and upper levels have fewer nodes so total work is O(n).

Compared this to "building cleanup". Not cleaning from top floor, but cleaning from bottom floors is efficient. Bottom floors already clean, just need to clean upper floors.

6. Real: Task Scheduler

My company code:

class TaskScheduler {
  constructor() {
    this.heap = new MaxHeap();
  }

  addTask(task) {
    this.heap.insert(task);
  }

  executeNext() {
    const task = this.heap.extractMax();
    console.log(`Executing: ${task.name} (Priority: ${task.priority})`);
    return task;
  }
}

const scheduler = new TaskScheduler();

scheduler.addTask({ name: 'Bug Fix', priority: 10 });
scheduler.addTask({ name: 'Feature', priority: 5 });
scheduler.addTask({ name: 'Critical Bug', priority: 15 });

scheduler.executeNext();  // Critical Bug (15)
scheduler.executeNext();  // Bug Fix (10)
scheduler.executeNext();  // Feature (5)

This was it: Task scheduler is Priority Queue, and Priority Queue's core is Heap. Using Heap instead of sorting every time drastically improved performance.

7. Heap vs Sorted Array

Sorted Array

const tasks = [5, 10, 15];

// Find max: O(1)
const max = tasks[tasks.length - 1];

// Insert: O(n) - must maintain sort
tasks.splice(index, 0, 12);  // Find right position

Problem: Insert slow!

For example, to insert 12 into [5, 10, 15]:

1. Find position for 12 (between 10 and 15)
2. Shift array tail one position
3. Insert 12

This is O(n).

Heap

// Find max: O(1)
const max = heap.heap[0];

// Insert: O(log n)
heap.insert(12);

Advantage: Insert/delete fast!

I compared this to "desk organization". Sorted array is library where books must always be alphabetically shelved. New book arrives, have to slide other books to insert in middle. But heap just follows rule "most important book on desk". Rest can be roughly piled, much faster.

8. Real: Top K Problem

Problem

"Find largest 10 from 1 million numbers"

❌ Bad (Sort)

const arr = [/* 1 million */];
arr.sort((a, b) => b - a);  // O(n log n) 😱
const top10 = arr.slice(0, 10);

Time: O(n log n)

• Sorts all 1 million (waste)

✅ Good (Min Heap)

class MinHeap {
  // (implementation omitted)
}

function topK(arr, k) {
  const heap = new MinHeap();

  arr.forEach(num => {
    heap.insert(num);

    if (heap.size() > k) {
      heap.extractMin();
    }
  });

  return heap.heap;
}

const top10 = topK(arr, 10);

Time: O(n log k)

• k=10 → O(n log 10) ≈ O(n) 🚀 fast!

"Why Min Heap?"

Initially confused. Finding max but using Min Heap? But thinking about it:

• Maintain size-10 Min Heap
• If new number larger than Heap's min, remove min and insert new number
• Eventually only largest 10 remain

I compared this to "university admission cutoff". Department with 10 spots, applicants keep coming. Current 10th student's score is cutoff. New applicant above cutoff gets in, 10th student drops out. Finally only top 10 remain.

9. Real: Dijkstra Algorithm

Shortest path algorithm uses Heap:

function dijkstra(graph, start) {
  const distances = { [start]: 0 };
  const heap = new MinHeap();
  heap.insert({ node: start, dist: 0 });

  while (heap.size() > 0) {
    const { node, dist } = heap.extractMin();

    graph[node].forEach(({ to, weight }) => {
      const newDist = dist + weight;

      if (!distances[to] || newDist < distances[to]) {
        distances[to] = newDist;
        heap.insert({ node: to, dist: newDist });
      }
    });
  }

  return distances;
}

Why Heap?

• Find nearest node in O(log n)
• Array would be O(n) (slow)

Dijkstra is "visit nearest node first" algorithm. Using Min Heap can always find shortest-distance node in O(log n).

10. Python heapq Module

Python has built-in heapq module:

import heapq

# Min Heap (default)
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heapq.heappop(heap))  # 1 (min)

# Max Heap (negative trick)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)

print(-heapq.heappop(max_heap))  # 5 (max)

Python's heapq only supports Min Heap. For Max Heap, use "convert to negative" trick. Put -3, -1, -5, then -5 is min, when extracting multiply by negative again to get 5 (max).

11. Finding Median with Two Heaps

Problem: Find median in real-time as numbers stream in

class MedianFinder {
  constructor() {
    this.maxHeap = new MaxHeap();  // smaller half
    this.minHeap = new MinHeap();  // larger half
  }

  addNum(num) {
    // Add to maxHeap first
    this.maxHeap.insert(num);

    // Move maxHeap's max to minHeap
    this.minHeap.insert(this.maxHeap.extractMax());

    // Balance sizes
    if (this.maxHeap.size() < this.minHeap.size()) {
      this.maxHeap.insert(this.minHeap.extractMin());
    }
  }

  findMedian() {
    if (this.maxHeap.size() > this.minHeap.size()) {
      return this.maxHeap.heap[0];
    } else {
      return (this.maxHeap.heap[0] + this.minHeap.heap[0]) / 2;
    }
  }
}

const mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
console.log(mf.findMedian());  // 1.5
mf.addNum(3);
console.log(mf.findMedian());  // 2

Idea:

• Max Heap: smaller half (Root = smaller half max)
• Min Heap: larger half (Root = larger half min)
• Two Heap Roots near median

I compared this to "seesaw balance". Distribute numbers so left (Max Heap) and right (Min Heap) weights stay similar. Median is average of two Heap Roots.

12. OS Process Scheduling

"Operating system uses Heap too!"

struct Process {
  int pid;
  int priority;
};

// CPU scheduler's Ready Queue = Priority Queue (Heap)
MaxHeap readyQueue;

void schedule() {
  while (true) {
    Process p = readyQueue.extractMax();  // highest priority process
    execute(p);
  }
}

OS process scheduler selects highest-priority process from Ready Queue and assigns to CPU. This Ready Queue is Priority Queue implemented with Heap.

I understood this as same as "ER waiting room". ER (CPU) is one but patients (processes) are many. From waiting room (Ready Queue), treat most critical (highest priority) patient first.

13. Heap Sort Algorithm O(n log n)

"Can sort with Heap too!"

function heapSort(arr) {
  const heap = new MaxHeap();

  // 1. Insert all elements into Heap - O(n log n)
  arr.forEach(num => heap.insert(num));

  // 2. Extract one by one filling array - O(n log n)
  const sorted = [];
  while (heap.size() > 0) {
    sorted.unshift(heap.extractMax());  // add to front (prevent descending)
  }

  return sorted;
}

console.log(heapSort([3, 1, 4, 1, 5, 9]));  // [1, 1, 3, 4, 5, 9]

More efficient (In-place Heap Sort):

function heapSort(arr) {
  const heap = new MaxHeap();
  heap.heapify(arr);  // O(n)

  for (let i = arr.length - 1; i > 0; i--) {
    // Move Root (max) to end
    [heap.heap[0], heap.heap[i]] = [heap.heap[i], heap.heap[0]];

    // Reduce heap size and bubbleDown
    heap.heap.length--;
    heap.bubbleDown(0);
  }

  return arr;
}

Time: O(n log n) Space: O(1) (In-place)

Heap Sort is O(n log n) sort like Merge Sort, Quick Sort, but has advantage of no extra memory needed.

14. K-way Merge

Problem: Merge k sorted arrays into one

function mergeKSortedArrays(arrays) {
  const heap = new MinHeap();
  const result = [];

  // Insert first element of each array into Heap
  arrays.forEach((arr, arrayIndex) => {
    if (arr.length > 0) {
      heap.insert({
        value: arr[0],
        arrayIndex: arrayIndex,
        elementIndex: 0
      });
    }
  });

  while (heap.size() > 0) {
    const { value, arrayIndex, elementIndex } = heap.extractMin();
    result.push(value);

    // If next element exists, insert into Heap
    const nextIndex = elementIndex + 1;
    if (nextIndex < arrays[arrayIndex].length) {
      heap.insert({
        value: arrays[arrayIndex][nextIndex],
        arrayIndex: arrayIndex,
        elementIndex: nextIndex
      });
    }
  }

  return result;
}

const arrays = [
  [1, 4, 7],
  [2, 5, 8],
  [3, 6, 9]
];

console.log(mergeKSortedArrays(arrays));  // [1, 2, 3, 4, 5, 6, 7, 8, 9]

Time: O(N log k)

• N = total elements
• k = number of arrays

Merging k arrays with Merge Sort is O(Nk), but using Heap reduces to O(N log k). I compared this to "multiple queues". Extract front person (min) from k queues, put next person from that queue. Repeat for total order.

15. JavaScript Built-in Heap?

Unfortunately no! 😢

// ❌ Not in JavaScript
const heap = new PriorityQueue();  // Error!

Solution:

1. Implement yourself (above code)
2. Libraries: heap-js, priorityqueuejs

npm install heap-js

const { Heap } = require('heap-js');

const maxHeap = new Heap((a, b) => b - a);
maxHeap.push(10);
maxHeap.push(5);
maxHeap.push(15);

console.log(maxHeap.pop());  // 15

Initially implementing heap in JavaScript, I wondered "Why no built-in Heap?" Python has heapq. Turns out JavaScript has relatively less Priority Queue demand so didn't include built-in. But many npm libraries exist.

Summary Checklist

Item	Description
Structure	Complete binary tree (array implementation)
Max Heap	Parent ≥ child (Root = max)
Min Heap	Parent ≤ child (Root = min)
Insert	O(log n) - Bubble Up
Delete	O(log n) - Bubble Down
Find Max	O(1) - Check Root
Heapify	O(n) - Convert array to heap
Use	Priority queue, Top K, Dijkstra, OS scheduling

Final: "No First-Come in ER"

Initially thought "Queue works, why Heap?"

Now see heaps everywhere:

• OS process scheduling = Heap
• Hospital ER = Priority Queue (Heap)
• Google search results = Top K (Heap)
• Dijkstra shortest path = Heap
• Real-time median calculation = Two Heaps

"Important things processed first."

This sentence IS heap essence.

Lesson learned:

"FIFO is fair, but Priority (Heap) is efficient."

Building task scheduler at work, biggest lesson was "sorting is overkill". Don't need to sort everything, just find most important thing right now quickly. That's heap philosophy.

Studying heap, I thought "data structures are philosophies". Array, linked list, tree, heap... each data structure has different worldview. Heap has worldview that "priority is everything".