Overview#

A heap is a complete binary tree that satisfies a specific ordering constraint, usually implemented with an array. It excels at the problem of dynamically maintaining the maximum or minimum value in a set of data.

Common heaps fall into two categories:

• Min-heap: each parent node is less than or equal to its children, and the top of the heap is the minimum value;
• Max-heap: each parent node is greater than or equal to its children, and the top of the heap is the maximum value.

Heaps are an important foundation for TopK, priority queues, task scheduling, merging sorted streams, and shortest path algorithms.

Prerequisites

• Complete binary tree: the structural basis of a heap
• Array index relationships: parent and child nodes can be computed from indices
• Priority queue: the most common engineering interface for a heap

Problem Definition#

If we need to repeatedly extract the current minimum or maximum element, a plain array has two obvious problems:

A heap sacrifices full ordering and only guarantees that the top of the heap is the global extremum, which allows it to achieve a better balance in dynamic scenarios.

Core Principle: Step-by-Step Illustration#

A heap is a complete binary tree that can be stored compactly in an array:

1
        1
2
      /   \
3
     3     5
4
    / \   /
5
   7   9 8
6

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

Array index relationships:

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

Detailed Algorithm Steps#

Min-heap insertion:

1. Append the element to the end of the array;
2. Set the current index to the new element’s position;
3. If the current element is smaller than its parent, swap;
4. Continue comparing upward until reaching the root or until the parent is smaller.

Min-heap pop:

1. Save the top of the heap as the return value;
2. Replace the top with the last element;
3. Starting from the root, compare with the smaller of the left and right children;
4. If the current node is larger, swap and continue sifting down;
5. After restoring the heap property, return the original top.

TypeScript Implementation#

1
class MinHeap<T> {
2
  private readonly data: T[] = [];
3

4
  constructor(private readonly compare: (a: T, b: T) => number) {}
5

6
  get size(): number {
7
    return this.data.length;
8
  }
9

10
  peek(): T | undefined {
11
    return this.data[0];
12
  }
13

14
  push(value: T): void {
15
    this.data.push(value);
16
    this.bubbleUp(this.data.length - 1);
17
  }
18

19
  pop(): T | undefined {
20
    if (this.data.length === 0) return undefined;
21
    if (this.data.length === 1) return this.data.pop();
22

23
    const root = this.data[0];
24
    this.data[0] = this.data.pop()!;
25
    this.sinkDown(0);
26
    return root;
27
  }
28

29
  private bubbleUp(index: number): void {
30
    while (index > 0) {
31
      const parent = Math.floor((index - 1) / 2);
32
      if (this.compare(this.data[index], this.data[parent]) >= 0) break;
33

34
      [this.data[index], this.data[parent]] = [this.data[parent], this.data[index]];
35
      index = parent;
36
    }
37
  }
38

39
  private sinkDown(index: number): void {
40
    while (true) {
41
      const left = index * 2 + 1;
42
      const right = index * 2 + 2;
43
      let smallest = index;
44

45
      if (left < this.data.length && this.compare(this.data[left], this.data[smallest]) < 0) {
46
        smallest = left;
47
      }
48

49
      if (right < this.data.length && this.compare(this.data[right], this.data[smallest]) < 0) {
50
        smallest = right;
51
      }
52

53
      if (smallest === index) break;
54

55
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
56
      index = smallest;
57
    }
58
  }
59
}

1
function topK(nums: number[], k: number): number[] {
2
  const heap = new MinHeap<number>((a, b) => a - b);
3

4
  for (const num of nums) {
5
    heap.push(num);
6

7
    if (heap.size > k) {
8
      heap.pop();
9
    }
10
  }
11

12
  const result: number[] = [];
13
  while (heap.size > 0) {
14
    result.push(heap.pop()!);
15
  }
16

17
  return result;
18
}

Engineering Optimization: Priority Queue Interface#

Many business scenarios do not directly care about the “heap” but about “the task with the highest priority executes first.” In this case, the heap can be encapsulated as a priority queue:

1
const queue = new MinHeap<{ priority: number; task: string }>(
2
  (a, b) => a.priority - b.priority,
3
);
4

5
queue.push({ priority: 10, task: 'low' });
6
queue.push({ priority: 1, task: 'high' });
7
console.log(queue.pop()?.task); // high

Using a comparison function as a constructor parameter allows the same heap implementation to support numbers, objects, and custom priorities.

Applications and Limitations#

Summary#

• A heap is a complete binary tree represented as an array.
• In a min-heap the top is the minimum value, and in a max-heap the top is the maximum value.
• Insertion relies on sifting up, and deleting the top relies on sifting down.
• A heap is suitable for dynamically maintaining extrema, not for full sorting.
• TopK and priority queues are the most common application scenarios for heaps.