Understanding Priority Queues and Binary Heaps with React Source Code

This article was first published on the ZooTeam frontend blog: "Combine React source code, master priority queues in five minutes".

What Is a Priority Queue

A priority queue is a fundamental data structure whose dequeue order depends on element priority rather than the FIFO order of a regular queue.

For example, React Fiber assigns priorities to rendering tasks; the order in which tasks are dequeued follows their importance, which is exactly what a priority queue provides.

Priority Queue Operations

Insert: add an element while keeping the queue ordered.

Delete max/min: remove and return the largest or smallest element while maintaining order.

Find max/min key: locate the element with the highest or lowest priority.

Implementation Comparison

Implementation

Insert

Delete

Find Max/Min

Array

O(1)

O(n)

O(n)

Linked List

O(1)

O(n)

O(1)

Sorted Array

O(n) or O(log n)

O(n)

O(1)

Sorted Linked List

O(n)

O(1)

O(1)

Binary Search Tree

O(log n)

O(log n)

O(log n)

Binary Heap

O(log n)

O(log n)

O(1)

Among these, binary heap offers logarithmic insert and delete operations and constant‑time access to the extremum, making it a practical choice for implementing priority queues.

Binary Heap

In a binary heap stored in an array, each element is less than (or greater than) its two children; the parent index of node k is ⌊k/2⌋ .

Binary heap properties:

Parent index of node k is k/2 (integer division).

The subtree rooted at any node contains the extremum of that subtree.

Binary Heap Operations

Insert (Push)

Insertion appends the new element at the end of the array and then "bubbles up" until the heap property is restored.

Example: inserting 9 into the heap shown above.

After swapping with its parent, the element continues bubbling up until the heap order is satisfied.

Final state after the second swap.

Program Skeleton

function push
  * add element at heap tail
  * perform bubble‑up loop
    * compare with parent and swap if necessary
  return minItem

Implementation

function push(heap: Heap, node: Node): void {
  const index = heap.length;
  heap.push(node); // add at tail
  siftUp(heap, node, index);
}

function siftUp(heap, node, i) {
  let index = i;
  while (true) {
    const parentIndex = (index - 1) >>> 1; // parent = child / 2
    const parent = heap[parentIndex];
    if (parent !== undefined && compare(parent, node) > 0) {
      // parent is larger, swap
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      return;
    }
  }
}

Delete (Pop)

Deletion removes the root, replaces it with the last element, and then "sinks" the new root to restore order.

Remove the root element.

Swap the last element with the root and delete the last slot.

Perform a down‑heap (sift‑down) operation.

Swap and delete steps illustrated.

Program Skeleton

function pop {
  * store root as minItem
  * replace root with last element and delete last element
  * perform down‑heap loop
    * compare with children and swap with the smaller one
  return minItem
}

Implementation

export function pop(heap: Heap): Node | null {
  const first = heap[0]; // root
  if (first !== undefined) {
    const last = heap.pop(); // remove tail
    if (last !== first) {
      heap[0] = last; // swap with root
      siftDown(heap, last, 0);
    }
    return first;
  } else {
    return null;
  }
}

function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  while (index < length) {
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];
    if (left !== undefined && compare(left, node) < 0) {
      if (right !== undefined && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (right !== undefined && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      return;
    }
  }
}

function compare(a, b) {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

Heap Sort

By repeatedly popping from a max/min heap, an array can be sorted in nlogn time.

Multi‑Way Heaps

To achieve better theoretical complexity, a binary heap can be generalized to a d‑ary heap. A ternary heap (d=3) reduces tree height K = log_d N , but larger d increases the cost of delete operations.

In libev, a four‑way heap is noted to be about 5 % more cache‑friendly when handling >50 000 watchers.

/*
 * at the moment we allow libev the luxury of two heaps,
 * a small-code-size 2-heap one and a ~1.5kb larger 4-heap
 * which is more cache‑efficient.
 * the difference is about 5% with 50000+ watchers.
 */

Go's timer implementation also uses a minimum four‑way heap.

Conclusion

For large data sets where cache performance matters, a d‑ary heap (especially a 4‑ary heap) can be advantageous. For smaller workloads with frequent inserts and deletes, a binary heap is usually sufficient.

Call to Action

If you found this article helpful, please click "Read Again" to increase its visibility.

Follow the public account "Zhoucai Cloud Frontend Team" for more curated technical content.

Recruitment

The Zhoucai Cloud Frontend Team (ZooTeam) is a young, passionate group based in Hangzhou, with over 40 frontend engineers averaging 27 years of age. We work on material systems, engineering platforms, performance, cloud applications, data analysis, and visualization, and we constantly explore new front‑end technologies.

If you are interested in joining us, send your resume to [email protected] .