Binary Heap

A complete binary tree that satisfies the heap property. Binary heaps are commonly used to implement priority queues, providing efficient access to the minimum or maximum element.

Overview

Binary heaps maintain a partial ordering where:

Min Heap: Parent is smaller than children (minimum at root)
Max Heap: Parent is larger than children (maximum at root)

The heap is stored as an array, using index arithmetic to navigate parent-child relationships.

Implementation

Base Class

class BinaryHeap<T = number> {
  heap: T[] = [];

  getLeftIndex(index: number) {
    return 2 * index + 1;
  }

  getRightIndex(index: number) {
    return 2 * index + 2;
  }

  getParentIndex(index: number) {
    if (index === 0) return null;
    return index % 2 === 0 ? (index - 2) / 2 : (index - 1) / 2;
  }
}

Reference: binary-heap.ts:1-20

Array Representation

Heap structure:       Array representation:
       1              [1, 3, 2, 7, 5, 4, 6]
      / \             
     3   2            Index: 0  1  2  3  4  5  6
    / \ / \
   7  5 4  6

For element at index i:
- Left child: 2i + 1
- Right child: 2i + 2  
- Parent: ⌊(i-1)/2⌛

Complete Binary Tree: All levels are fully filled except possibly the last, which is filled from left to right. This property allows efficient array storage without gaps.

Min Heap

A heap where the parent is always smaller than its children.

API Reference

insert(value: T): void

Inserts a value and maintains the min-heap property.

const minHeap = new MinHeap<number>();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(7);
minHeap.insert(1);

console.log(minHeap.heap); // [1, 3, 7, 5]
//       1
//      / \
//     3   7
//    /
//   5

Algorithm:

Add element to end of array
“Sift up” by comparing with parent
Swap if smaller than parent
Repeat until heap property restored

Complexity: O(log n) Reference: min-heap.ts:4-8

extract(): T | null

Removes and returns the minimum element (root).

const minHeap = new MinHeap<number>();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(7);
minHeap.insert(1);

console.log(minHeap.extract()); // 1
console.log(minHeap.extract()); // 3
console.log(minHeap.extract()); // 5

Algorithm:

Save root element to return
Move last element to root
“Sift down” by comparing with children
Swap with smaller child if necessary
Repeat until heap property restored

Complexity: O(log n) Reference: min-heap.ts:10-27

Internal Methods

siftUp(index)

Moves an element up the tree to maintain heap property.

#siftUp(index: number) {
  let parentIndex = this.getParentIndex(index);

  while (parentIndex !== null && this.heap[parentIndex] > this.heap[index]) {
    this.#swap(parentIndex, index);
    index = parentIndex;
    parentIndex = this.getParentIndex(index);
  }
}

Reference: min-heap.ts:29-37

siftDown(index)

Moves an element down the tree to maintain heap property.

#siftDown(index: number) {
  let leftIndex = this.getLeftIndex(index);
  let rightIndex = this.getRightIndex(index);
  let smallest = index;

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

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

  if (smallest !== index) {
    this.#swap(smallest, index);
    this.#siftDown(smallest);
  }
}

Reference: min-heap.ts:39-62

Max Heap

A heap where the parent is always larger than its children.

API Reference

insert(value: T): void

Inserts a value and maintains the max-heap property.

const maxHeap = new MaxHeap<number>();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(7);
maxHeap.insert(1);

console.log(maxHeap.heap); // [7, 5, 3, 1]
//       7
//      / \
//     5   3
//    /
//   1

Complexity: O(log n) Reference: max-heap.ts:4-8

extract(): T | null

Removes and returns the maximum element (root).

const maxHeap = new MaxHeap<number>();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(7);
maxHeap.insert(1);

console.log(maxHeap.extract()); // 7
console.log(maxHeap.extract()); // 5
console.log(maxHeap.extract()); // 3

Complexity: O(log n) Reference: max-heap.ts:10-27

Complexity Summary

Operation	Time Complexity	Space Complexity
insert	O(log n)	O(1)
extract	O(log n)	O(1)
peek (access root)	O(1)	O(1)
build heap	O(n)	O(1)
search	O(n)	O(1)

Why O(log n)? The heap height is log n because it’s a complete binary tree. Sifting up or down traverses at most one path from root to leaf.

Common Use Cases

Priority Queue

class PriorityQueue<T> {
  private heap = new MinHeap<{ priority: number; value: T }>();
  
  enqueue(value: T, priority: number) {
    this.heap.insert({ priority, value });
  }
  
  dequeue(): T | null {
    const item = this.heap.extract();
    return item ? item.value : null;
  }
  
  peek(): T | null {
    return this.heap.heap[0]?.value ?? null;
  }
}

const pq = new PriorityQueue<string>();
pq.enqueue('Low priority task', 10);
pq.enqueue('High priority task', 1);
pq.enqueue('Medium priority task', 5);

console.log(pq.dequeue()); // 'High priority task'

Top K Elements

function findKLargest(nums: number[], k: number): number[] {
  const minHeap = new MinHeap<number>();
  
  for (const num of nums) {
    minHeap.insert(num);
    
    // Keep heap size at k
    if (minHeap.heap.length > k) {
      minHeap.extract();
    }
  }
  
  return minHeap.heap;
}

// Example: Find 3 largest in [3, 1, 5, 12, 2, 11]
console.log(findKLargest([3, 1, 5, 12, 2, 11], 3)); // [5, 11, 12]

Heap Sort

function heapSort(arr: number[]): number[] {
  const maxHeap = new MaxHeap<number>();
  
  // Build heap
  for (const num of arr) {
    maxHeap.insert(num);
  }
  
  // Extract in sorted order
  const sorted: number[] = [];
  while (maxHeap.heap.length > 0) {
    sorted.unshift(maxHeap.extract()!);
  }
  
  return sorted;
}

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

Median Finder

class MedianFinder {
  private maxHeap = new MaxHeap<number>(); // Stores smaller half
  private minHeap = new MinHeap<number>(); // Stores larger half
  
  addNum(num: number) {
    // Add to max heap (smaller half)
    this.maxHeap.insert(num);
    
    // Balance: largest of smaller half goes to larger half
    this.minHeap.insert(this.maxHeap.extract()!);
    
    // Ensure max heap has equal or one more element
    if (this.maxHeap.heap.length < this.minHeap.heap.length) {
      this.maxHeap.insert(this.minHeap.extract()!);
    }
  }
  
  findMedian(): number {
    if (this.maxHeap.heap.length > this.minHeap.heap.length) {
      return this.maxHeap.heap[0];
    }
    return (this.maxHeap.heap[0] + this.minHeap.heap[0]) / 2;
  }
}

Heap vs BST

Feature	Binary Heap	Binary Search Tree
Ordering	Partial (heap property)	Total (sorted)
Find min/max	O(1)	O(log n) to O(n)
Find arbitrary	O(n)	O(log n) to O(n)
Insert	O(log n)	O(log n) to O(n)
Delete min/max	O(log n)	O(log n) to O(n)
Delete arbitrary	O(n)	O(log n) to O(n)
Storage	Array (compact)	Nodes with pointers
Use case	Priority queues	Sorted data, range queries

When to use heaps:

Need quick access to min/max element
Implementing priority queues
Don’t need to search for arbitrary elements
Want compact array storage

Visualization: Insert Operation

Min Heap Insert Example

Insert 2 into heap [3, 5, 7, 9, 8]:

Step 1: Add to end
       3
      / \
     5   7
    / \ /
   9  8 2

Array: [3, 5, 7, 9, 8, 2]
                        ^
                     added here

Step 2: Compare with parent (7)
2 < 7, so swap

       3
      / \
     5   2
    / \ /
   9  8 7

Array: [3, 5, 2, 9, 8, 7]

Step 3: Compare with parent (3)
2 < 3, so swap

       2
      / \
     5   3
    / \ /
   9  8 7

Array: [2, 5, 3, 9, 8, 7]

Done! (2 is at root, heap property satisfied)

Key Characteristics

Advantages:

O(1) access to min/max element
O(log n) insert and delete
Compact array storage (no pointers)
Cache-friendly due to array representation
Simple to implement

Limitations:

O(n) search for arbitrary elements
No efficient way to increase/decrease arbitrary elements
Not sorted (only partial ordering)
Extract operations destroy the structure

When to Use Binary Heaps

Priority Queues

When you need to efficiently process items by priority (task scheduling, event handling).

Binary Search Tree

Total ordering for sorted operations

AVL Tree

Self-balancing for arbitrary lookups

Queue

FIFO queue (heap enables priority queue)

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

Binary Heap

Binary Heap

Overview

Implementation

Base Class

Array Representation

Min Heap

API Reference

insert(value: T): void

extract(): T | null

Internal Methods

siftUp(index)

siftDown(index)

Max Heap

API Reference

insert(value: T): void

extract(): T | null

Complexity Summary

Common Use Cases

Priority Queue

Top K Elements

Heap Sort

Median Finder

Heap vs BST

Visualization: Insert Operation

Min Heap Insert Example

Key Characteristics

When to Use Binary Heaps

Binary Search Tree

AVL Tree

Queue

Build docs developers (and LLMs) love

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

​Binary Heap

​Overview

​Implementation

​Base Class

​Array Representation

​Min Heap

​API Reference

​insert(value: T): void

​extract(): T | null

​Internal Methods

​siftUp(index)

​siftDown(index)

​Max Heap

​API Reference

​insert(value: T): void

​extract(): T | null

​Complexity Summary

​Common Use Cases

​Priority Queue

​Top K Elements

​Heap Sort

​Median Finder

​Heap vs BST

​Visualization: Insert Operation

​Min Heap Insert Example

​Key Characteristics

​When to Use Binary Heaps

​Related Data Structures

Binary Search Tree

AVL Tree

Queue

Build docs developers (and LLMs) love

Binary Heap

Overview

Implementation

Base Class

Array Representation

Min Heap

API Reference

insert(value: T): void

extract(): T | null

Internal Methods

siftUp(index)

siftDown(index)

Max Heap

API Reference

insert(value: T): void

extract(): T | null

Complexity Summary

Common Use Cases

Priority Queue

Top K Elements

Heap Sort

Median Finder

Heap vs BST

Visualization: Insert Operation

Min Heap Insert Example

Key Characteristics

When to Use Binary Heaps

Related Data Structures