Understanding Heap Data Structure

In my React Deep Dive series, I mentioned that React Fiber's scheduler uses a min-heap data structure to manage and prioritize tasks in its concurrent rendering model. Let's explore how heaps work and why they're perfect for this use case.

What is a Heap?

A heap is a complete binary tree that satisfies the heap property:

  • Min-Heap: Every parent node is ≤ its children
  • Max-Heap: Every parent node is ≥ its children

Array Representation

Heaps are efficiently stored as arrays. For any element at index i:

  • Parent: Math.floor((i - 1) / 2)
  • Left Child: 2 * i + 1
  • Right Child: 2 * i + 2
1// Example: Given the array [10, 5, 3, 2, 4]
2// The tree structure is:
3//       10
4//      /  \
5//     5    3
6//    / \
7//   2   4
8
9// Array indices:
10// [0] = 10  (root)
11// [1] = 5   (left child of 10)
12// [2] = 3   (right child of 10)
13// [3] = 2   (left child of 5)
14// [4] = 4   (right child of 5)

Why Heaps in React Fiber?

React Fiber needs to:

  1. Prioritize updates (e.g., user input > animations > background data fetching)
  2. Interrupt/pause low-priority work if high-priority work arrives
  3. Schedule tasks efficiently to avoid jank (e.g., dropping frames)

A min-heap (priority queue) is ideal for this because:

  • It ensures the highest-priority task is always processed next (O(1) peek)
  • Insertion/extraction is O(log n), which is efficient for dynamic task queues

Implementing a Min-Heap

Let's implement a min-heap and solve LeetCode 215 (Kth Largest Element in an Array) to demonstrate its usage:

1class MinHeap {
2  constructor() {
3      this.heap = [];
4  }
5
6  // Get parent index
7  getParentIndex(i) {
8      return Math.floor((i - 1) / 2);
9  }
10
11  // Get left child index
12  getLeftChildIndex(i) {
13      return 2 * i + 1;
14  }
15
16  // Get right child index
17  getRightChildIndex(i) {
18      return 2 * i + 2;
19  }
20
21  // Swap two elements
22  swap(i, j) {
23      [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
24  }
25
26  // Insert a new element
27  insert(value) {
28      this.heap.push(value);
29      this.heapifyUp();
30  }
31
32  // Remove and return the minimum element
33  extractMin() {
34      if (this.heap.length === 0) return null;
35      
36      const min = this.heap[0];
37      const last = this.heap.pop();
38      
39      if (this.heap.length > 0) {
40          this.heap[0] = last;
41          this.heapifyDown();
42      }
43      
44      return min;
45  }
46
47  // Move an element up to maintain heap property
48  heapifyUp() {
49      let currentIndex = this.heap.length - 1;
50      
51      while (currentIndex > 0) {
52          const parentIndex = this.getParentIndex(currentIndex);
53          
54          if (this.heap[parentIndex] <= this.heap[currentIndex]) {
55              break;
56          }
57          
58          this.swap(parentIndex, currentIndex);
59          currentIndex = parentIndex;
60      }
61  }
62
63  // Move an element down to maintain heap property
64  heapifyDown() {
65      let currentIndex = 0;
66      
67      while (true) {
68          let smallestIndex = currentIndex;
69          const leftChildIndex = this.getLeftChildIndex(currentIndex);
70          const rightChildIndex = this.getRightChildIndex(currentIndex);
71          
72          if (leftChildIndex < this.heap.length && 
73              this.heap[leftChildIndex] < this.heap[smallestIndex]) {
74              smallestIndex = leftChildIndex;
75          }
76          
77          if (rightChildIndex < this.heap.length && 
78              this.heap[rightChildIndex] < this.heap[smallestIndex]) {
79              smallestIndex = rightChildIndex;
80          }
81          
82          if (smallestIndex === currentIndex) {
83              break;
84          }
85          
86          this.swap(currentIndex, smallestIndex);
87          currentIndex = smallestIndex;
88      }
89  }
90}

Solving LeetCode 215

Let's use our min-heap to find the kth largest element:

1function findKthLargest(nums, k) {
2  const minHeap = new MinHeap();
3  
4  // Keep only k elements in the heap
5  for (const num of nums) {
6      minHeap.insert(num);
7      if (minHeap.heap.length > k) {
8          minHeap.extractMin();
9      }
10  }
11  
12  return minHeap.heap[0];
13}
14
15// Example usage:
16const nums = [3, 2, 1, 5, 6, 4];
17const k = 2;
18console.log(findKthLargest(nums, k)); // Output: 5

How React Fiber Uses Heaps

React's scheduler uses a min-heap to manage task priorities:

1// Simplified version of React's scheduler
2class Scheduler {
3  constructor() {
4      this.taskQueue = new MinHeap();
5  }
6
7  scheduleTask(priority, task) {
8      this.taskQueue.insert({ priority, task });
9  }
10
11  processNextTask() {
12      const { task } = this.taskQueue.extractMin();
13      task();
14  }
15}
16
17// Usage in React Fiber
18const scheduler = new Scheduler();
19
20// High priority task (user interaction)
21scheduler.scheduleTask(1, () => {
22  // Handle user input
23});
24
25// Low priority task (background update)
26scheduler.scheduleTask(5, () => {
27  // Update background data
28});

Time Complexity

  • Insertion: O(log n)
  • Extraction: O(log n)
  • Peek (get min/max): O(1)
  • Heapify: O(n)

Space Complexity

  • O(n) for storing the heap

Real-World Applications

  1. React Fiber Scheduler

    • Task prioritization
    • Efficient task scheduling
    • Interruptible rendering

  2. Operating Systems

    • Process scheduling
    • Priority queues
    • Event handling

  3. Graph Algorithms

    • Dijkstra's algorithm
    • Prim's algorithm
    • A* pathfinding

Conclusion

Heaps are a fundamental data structure that powers many real-world applications, including React's concurrent rendering model. Their efficient O(log n) operations and O(1) access to the highest/lowest priority element make them ideal for task scheduling and prioritization.