HeapsLesson 1

How Heaps Work

A complete binary tree stored in an array where every parent is larger (or smaller) than its children. The structure behind priority queues.

What Is It?

A heap is a tree with one rule: every parent is bigger than (or equal to) its children. That's it.

Because of that rule, the biggest value always sits at the top. You can look at it instantly. This makes a heap the perfect tool when you repeatedly need to grab the largest (or smallest) item.

A max-heap — every parent is bigger than its children. The top is the maximum.
A min-heap — every parent is smaller than its children. The top is the minimum.

There's no rule about left vs. right children. The only constraint is parent vs. its own children.

A heap is also called a priority queue — a structure that always lets you pull out the highest-priority item next.

Analogy

The Corporate Pyramid

Imagine a company where every manager earns more than their direct reports. The CEO earns the most and sits at the top.

There's no rule about people at the same level. The VP of Engineering might earn more or less than the VP of Marketing. But any manager is always paid more than the people directly under them.

Now say the CEO leaves. You can't leave the top empty. So you temporarily promote the most junior employee to CEO. Obviously they don't belong there. So they "compete" with their two direct reports — whoever earns more takes the CEO role. The loser then competes with their own reports. This keeps going until the salary order is restored.

That process of pushing someone down through the tree is exactly how a heap fixes itself after removing the top.

Try It Yourself

Empty heap — insert values

How It Works

The Heap Rule

Max-Heap

Every parent is greater than or equal to its children
Root holds the largest element
Used when you need to repeatedly extract the maximum

Root is always the maximum value

parent >= children

Min-Heap

Every parent is less than or equal to its children
Root holds the smallest element
Used when you need to repeatedly extract the minimum

Root is always the minimum value

parent <= children

A heap is NOT a binary search tree. In a BST, left children are smaller and right children are bigger — there's a strict left-right ordering. In a heap, there's no left-right ordering at all. The only rule is parent vs. its children:

Binary Search Tree

Left child is always less than parent
Right child is always greater than parent
Enables efficient search: O(log n)
Ordering applies to ALL descendants

Strict left-right ordering

left < parent < right

Heap

Only constraint: parent >= children (max-heap)
Left child can be greater than right child
Cannot efficiently search for arbitrary values
Ordering only between parent and direct children

No left-right relationship

parent >= left AND parent >= right

Heaps Are Stored as Arrays

Here's the clever part. A heap looks like a tree conceptually, but it's stored as a plain array. No pointers. No objects with left and right fields. Just an array.

This works because of one constraint: a heap must be a complete binary tree — every level is fully filled except possibly the last, which fills from left to right with no gaps.

Valid (Complete)

All levels fully filled except possibly the last
Last level filled from left to right with no gaps
Array representation works perfectly
Example: [90, 70, 80, 50, 60, 40]

Every level fully filled, last level filled left to right

complete binary tree

Invalid (Not Complete)

Last level has a gap (missing left child)
Nodes not filled left to right
Array representation breaks down
Index math for parent/child no longer works

Gap in the last level breaks completeness

not a complete binary tree

Because the tree is always complete and has no gaps, you can number the nodes level by level and store them in that order:

Tree View

Root: 90
Level 1: 70, 80
Level 2: 50, 60, 40
Parent of index i: (i-1)/2
Left child: 2*i+1
Right child: 2*i+2

Conceptual representation of the heap

nodes with parent-child relationships

Array View

How the heap is actually stored in memory

flat array, no pointers needed

With this numbering, you can find any node's parent or children using simple math:

pseudocode

For a node at index i:
  Parent is at:      (i - 1) / 2   (using integer division)
  Left child is at:  2 * i + 1
  Right child is at: 2 * i + 2

Let's verify with the tree [90, 70, 80, 50, 60, 40]:

pseudocode

Node at index 1 (value 70):
  Parent: (1-1)/2 = 0  -> value 90  (correct, 90 is the root)
  Left:   2*1+1   = 3  -> value 50  (correct)
  Right:  2*1+2   = 4  -> value 60  (correct)
Node at index 2 (value 80):
  Parent: (2-1)/2 = 0  -> value 90  (correct)
  Left:   2*2+1   = 5  -> value 40  (correct)
  Right:  2*2+2   = 6  -> beyond array, no right child

No pointers needed — just arithmetic. This is why heaps are fast and memory-efficient.

Heap as a Priority Queue

A priority queue is a structure with three operations:

INSERT: Add an item
PEEK: See the top item without removing it
EXTRACT: Remove and return the top item

A heap implements all three efficiently:

Heap

Insert: O(log n)
Peek: O(1)
Extract: O(log n)

balanced trade-off

Sorted Array

Insert: O(n)
Peek: O(1)
Extract: O(1)*

fast reads, slow writes

Unsorted Array

Insert: O(1)
Peek: O(n)
Extract: O(n)

fast writes, slow reads

A heap gives you the best trade-off — O(log n) for both insert and extract.

The Basic Structure

pseudocode

class MaxHeap:
    array = []         // stores the elements
    size = 0           // how many elements are in the heap
    
    function parent(i):
        return (i - 1) / 2
    
    function leftChild(i):
        return 2 * i + 1
    
    function rightChild(i):
        return 2 * i + 2
    
    function peek():
        if size == 0:
            error "Heap is empty"
        return array[0]    // Always O(1)

The insert and extract operations (with their sift-up and sift-down steps) are covered in the next lesson.

A Larger Example

pseudocode

Max-heap with 9 elements:
Tree view:
                  100
                /     \
              85        90
            /    \     /  \
          70     80   50   60
         /  \
       30   40
Array view:
Index:  0    1    2    3    4    5    6    7    8
      [100,  85,  90,  70,  80,  50,  60,  30,  40]
Verify heap property:
  100 >= 85 and 100 >= 90  (root)
   85 >= 70 and  85 >= 80  (index 1)
   90 >= 50 and  90 >= 60  (index 2)
   70 >= 30 and  70 >= 40  (index 3)

When to Use a Heap

You need to repeatedly get the largest or smallest item
Finding the k-th largest or smallest element
Merging multiple sorted lists
Dijkstra's shortest path algorithm
Any problem where "what's the current best option?" drives the algorithm

Examples

Example 1: Is this a valid max-heap?

pseudocode

Array: [50, 30, 40, 10, 20, 35, 38]
Tree:
        50
       /  \
      30   40
     / \   / \
   10  20 35  38
Check every parent >= its children:
  50 >= 30? yes   50 >= 40? yes
  30 >= 10? yes   30 >= 20? yes
  40 >= 35? yes   40 >= 38? yes
Valid max-heap!

Example 2: Not a valid max-heap

pseudocode

Array: [50, 30, 40, 10, 20, 45, 38]
Tree:
        50
       /  \
      30   40
     / \   / \
   10  20 45  38
Check: 40 >= 45? NO! 45 > 40, which means a child is bigger than its parent.
Not a valid max-heap!

Example 3: Converting between tree and array

pseudocode

Given this tree, write the array:
        75
       /  \
      60   65
     / \
    40  50
Read level by level: 75, 60, 65, 40, 50
Array: [75, 60, 65, 40, 50]
Given this array, draw the tree:
[80, 70, 60, 50, 65, 55, 40]
Index 0 = root = 80
Index 1 = left child of root = 70
Index 2 = right child of root = 60
Index 3 = left child of index 1 = 50
Index 4 = right child of index 1 = 65
Index 5 = left child of index 2 = 55
Index 6 = right child of index 2 = 40
         80
        /  \
      70    60
     / \    / \
   50  65  55  40

Common Mistakes

Confusing heaps with BSTs. A heap does NOT have the BST property. In a max-heap, the left child can be greater than the right child. You cannot efficiently search for a specific value in a heap.

Thinking the heap array is sorted. The array [90, 70, 80, 50, 60, 40] is a valid heap but NOT sorted. Only the first element (the root) is guaranteed to be the largest. The rest are only partially ordered.

Forgetting the completeness requirement. The array representation only works if the tree is complete — no gaps. A tree where parents are all greater than children but has gaps in the last level is NOT a valid heap.

Assuming the second-largest element is at index 1. It could be at index 1 or index 2 — either child of the root. There's no guarantee which one is larger.

Best Practices

Choose max-heap when you need to repeatedly extract the largest item; choose min-heap for the smallest
Always verify the heap property by checking every parent-child pair — a single violation breaks the whole structure
Remember that a heap gives O(1) access to the root only — finding any other value takes O(n)
When you need the k largest elements, consider a min-heap of size k — counterintuitively, it lets you efficiently drop the smallest of your candidates

Runnable Code

Here is a complete JavaScript MinHeap implementation you can run. It covers insert (with bubble up), extract min (with sink down), and peek.

Min Heap — Full Implementation

class MinHeap {
  constructor() {
    this.heap = [];
  }
  parent(i) { return Math.floor((i - 1) / 2); }
  leftChild(i) { return 2 * i + 1; }
  rightChild(i) { return 2 * i + 2; }
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
  // Insert and bubble up
  insert(val) {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0 && this.heap[i] < this.heap[this.parent(i)]) {
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }
  // Remove min and sink down
  extractMin() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this._sinkDown(0);
    return min;
  }
  _sinkDown(i) {
    const n = this.heap.length;
    let smallest = i;
    const left = this.leftChild(i);
    const right = this.rightChild(i);
    if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
    if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
    if (smallest !== i) {
      this.swap(i, smallest);
      this._sinkDown(smallest);
    }
  }
  peek() { return this.heap.length > 0 ? this.heap[0] : null; }
  size() { return this.heap.length; }
}
// --- Demo ---
const heap = new MinHeap();
const values = [15, 10, 20, 8, 25, 5];
console.log('--- Inserting values ---');
for (const v of values) {
  heap.insert(v);
  console.log('Insert ' + v + ' -> heap: [' + heap.heap.join(', ') + ']');
}
console.log('\nMin (peek):', heap.peek());
console.log('\n--- Extracting in sorted order ---');
while (heap.size() > 0) {
  const min = heap.extractMin();
  console.log('Extract:', min, ' remaining: [' + heap.heap.join(', ') + ']');
}

Tree Traversals — BFS Heap Operations