Efficient Event and Task Scheduling with a Min-Binary Heap in JavaScript

When orchestrating concurrent asynchronous tasks, scheduling browser animations, or routing pathfinding nodes, client-side applications frequently need to evaluate items in order of urgent priority. A standard shortcut in JavaScript is pushing elements into a regular array and calling array.sort() whenever the highest-priority item is required. Because quicksort and Timsort execute in $O(n \log n)$ time, re-sorting on every job arrival or cycle triggers severe computational penalties and stalls task dispatch loops on high-throughput workloads.

A binary min-heap offers the ideal algorithmic foundation for priority queues. Represented compactly within a contiguous array, the root node occupies index 0, with children of index $i$ mapped mathematically to indices $2i + 1$ and $2i + 2$, and parents located at $\lfloor (i - 1) / 2 \rfloor$. By maintaining the invariant where every parent evaluates smaller than or equal to its children, the heap achieves instant $O(1)$ inspection of the minimum item alongside $O(\log n)$ insertion and extraction via efficient bubble-up and sink-down element swaps.

Example #

import { PriorityQueue } from './PriorityQueue.js';

// Instantiate min-heap prioritized by scheduled timestamp
const taskScheduler = new PriorityQueue((a, b) => a.timestamp - b.timestamp);

// Enqueue asynchronous jobs with varied due times
taskScheduler.enqueue({ name: 'Sync telemetry', timestamp: 1718899200000 });
taskScheduler.enqueue({ name: 'Urgent user payment', timestamp: 1718895600000 });
taskScheduler.enqueue({ name: 'Background indexing', timestamp: 1718902800000 });

// Peek at the most urgent pending task without removing it
console.log(taskScheduler.peek().name); // 'Urgent user payment'

// Dequeue and process tasks in strict priority order
while (!taskScheduler.isEmpty()) {
  const currentJob = taskScheduler.dequeue();
  console.log(`Processing ${currentJob.name} (${currentJob.timestamp})`);
}

Implementation #

/**
 * Zero-dependency generic Priority Queue backed by a binary heap.
 * Supports custom comparator functions for min-heap or max-heap behaviors.
 */
export class PriorityQueue {
  /**
   * @param {Function} [comparator] - Function returning negative if a < b, positive if a > b.
   * Defaults to a standard ascending number comparator.
   */
  constructor(comparator = (a, b) => a - b) {
    this._heap = [];
    this._comparator = comparator;
  }

  /**
   * Returns current count of queued items.
   * @returns {number}
   */
  get size() {
    return this._heap.length;
  }

  /**
   * Checks if queue has zero items.
   * @returns {boolean}
   */
  isEmpty() {
    return this._heap.length === 0;
  }

  /**
   * Inspects the highest-priority element in O(1) time.
   * @returns {*|undefined}
   */
  peek() {
    return this._heap[0];
  }

  /**
   * Inserts an item into the queue in O(log n) time.
   * Appends to end of array and bubbles up until heap property is restored.
   * @param {*} value
   */
  enqueue(value) {
    this._heap.push(value);
    this._bubbleUp(this._heap.length - 1);
  }

  /**
   * Extracts and returns the highest-priority element in O(log n) time.
   * Swaps root with final leaf, pops leaf, and sinks new root down.
   * @returns {*|undefined}
   */
  dequeue() {
    if (this.isEmpty()) return undefined;

    const root = this._heap[0];
    const bottom = this._heap.pop();

    if (this._heap.length > 0) {
      this._heap[0] = bottom;
      this._sinkDown(0);
    }

    return root;
  }

  /**
   * Swaps two array elements in-place.
   * @private
   */
  _swap(i, j) {
    const temp = this._heap[i];
    this._heap[i] = this._heap[j];
    this._heap[j] = temp;
  }

  /**
   * Restores heap property upward from newly inserted index.
   * @private
   */
  _bubbleUp(index) {
    let current = index;

    while (current > 0) {
      const parent = Math.floor((current - 1) / 2);

      // If current is higher priority than parent, swap
      if (this._comparator(this._heap[current], this._heap[parent]) < 0) {
        this._swap(current, parent);
        current = parent;
      } else {
        break;
      }
    }
  }

  /**
   * Restores heap property downward from index after root removal.
   * @private
   */
  _sinkDown(index) {
    const length = this._heap.length;
    let current = index;

    while (true) {
      const leftChild = 2 * current + 1;
      const rightChild = 2 * current + 2;
      let highestPriority = current;

      if (
        leftChild < length &&
        this._comparator(this._heap[leftChild], this._heap[highestPriority]) < 0
      ) {
        highestPriority = leftChild;
      }

      if (
        rightChild < length &&
        this._comparator(this._heap[rightChild], this._heap[highestPriority]) < 0
      ) {
        highestPriority = rightChild;
      }

      if (highestPriority !== current) {
        this._swap(current, highestPriority);
        current = highestPriority;
      } else {
        break;
      }
    }
  }
}

// Concrete application: Async task scheduler with priority leveling
class AsyncTaskScheduler {
  constructor() {
    // Items with lowest priority numbers are executed first (1 = critical, 5 = low)
    this.queue = new PriorityQueue((a, b) => a.priority - b.priority);
    this.isProcessing = false;
  }

  scheduleTask(id, priority, taskFn) {
    this.queue.enqueue({ id, priority, taskFn, addedAt: Date.now() });
    this.processNext();
  }

  async processNext() {
    if (this.isProcessing || this.queue.isEmpty()) return;
    this.isProcessing = true;

    const current = this.queue.dequeue();
    try {
      console.log(`Executing Task [${current.id}] (Priority ${current.priority})`);
      await current.taskFn();
    } catch (err) {
      console.error(`Task [${current.id}] failed:`, err);
    } finally {
      this.isProcessing = false;
      this.processNext();
    }
  }
}

// Verification simulation
const scheduler = new AsyncTaskScheduler();
scheduler.scheduleTask('log-analytics', 3, () => new Promise(r => setTimeout(r, 50)));
scheduler.scheduleTask('auth-token-refresh', 1, () => new Promise(r => setTimeout(r, 50)));
scheduler.scheduleTask('render-frame', 2, () => new Promise(r => setTimeout(r, 50)));

Main Point: Implementing a binary min-heap Priority Queue in JavaScript reduces insertion and extraction costs to logarithmic time while delivering predictable O(1) peek performance for mission-critical scheduling engines.

Credits #

Photo by Pawel Czerwinski on Unsplash

← Home