https://news.ycombinator.com/item?id=45717754

README.md

deno bench heap-bench.js

benchmark	time/iter (avg)	iter/s	(min … max)	p75	p99	p995
heap	9.6 µs	104,000	( 8.7 µs … 172.2 µs)	9.2 µs	16.1 µs	18.9 µs
redundant sort and shift	1.3 ms	746.0	( 1.3 ms … 1.5 ms)	1.3 ms	1.4 ms	1.5 ms
sort once and pop	26.9 µs	37,130	( 25.5 µs … 160.7 µs)	26.6 µs	35.7 µs	42.1 µs
buckets	4.6 µs	219,000	( 4.5 µs … 4.7 µs)	4.6 µs	4.7 µs	4.7 µs

heap-bench.js

class Item {
	constructor(runner, priority) {
		this.runner = runner;
		this.priority = priority;
	}
}

const heapPush = (heap, item) => {
	heap.push(item);

	for (let i = heap.length - 1; i > 0;) {
		const p = (i - 1) >>> 1;

		if (heap[i].priority >= heap[p].priority) {
			break;
		}

		const t = heap[i];
		heap[i] = heap[p];
		heap[p] = t;
		i = p;
	}
};

const heapPop = heap => {
	if (heap.length === 1) {
		return heap.pop();
	}

	const top = heap[0];
	heap[0] = heap.pop();

	for (let i = 0;;) {
		const l = 2 * i + 1;
		let min = i;

		if (l < heap.length && heap[l].priority < heap[min].priority) {
			min = l;
		}

		if (l + 1 < heap.length && heap[l + 1].priority < heap[min].priority) {
			min = l + 1;
		}

		if (min === i) {
			break;
		}

		const t = heap[i];
		heap[i] = heap[min];
		heap[min] = t;
		i = min;
	}

	return top;
};

const comparePriority = (a, b) => a.priority - b.priority;
const comparePriorityReversed = (a, b) => b.priority - a.priority;

const PRIORITIES = [-10000, 0, 10000];

const RUNNER = () => {};
const N = 400;
const PRIORITY_SEQUENCE = Array.from({length: N}, () => PRIORITIES[Math.floor(Math.random() * PRIORITIES.length)]);

Deno.bench('heap', () => {
	const pq = [];

	for (let i = 0; i < N; i++) {
		heapPush(pq, new Item(RUNNER, PRIORITY_SEQUENCE[i]));
	}

	while (pq.length !== 0) {
		(0, heapPop(pq).runner)();
	}
});

Deno.bench('redundant sort and shift', () => {
	const pq = [];

	for (let i = 0; i < N; i++) {
		pq.push(new Item(RUNNER, PRIORITY_SEQUENCE[i]));
	}

	while (pq.length !== 0) {
		pq.sort(comparePriority);
		(0, pq.shift().runner)();
	}
});

// unlike the other implementations in this benchmark, this one doesn't support runners that enqueue new tasks for the same frame
Deno.bench('sort once and pop', () => {
	const pq = [];

	for (let i = 0; i < N; i++) {
		pq.push(new Item(RUNNER, PRIORITY_SEQUENCE[i]));
	}

	pq.sort(comparePriorityReversed);

	while (pq.length !== 0) {
		(0, pq.pop().runner)();
	}
});

// A quick look at github.com/microsoft/vscode suggests it might only use these three priority levels?
// This implementation's queues can grow arbitrarily large with badly behaved tasks, but it's easy to swap in a growable circular buffer or something.
{
	const queues = PRIORITIES.map(() => []);
	const DIRTY_NONE = PRIORITIES.length;
	let dirty = DIRTY_NONE;

	const push = item => {
		const i = PRIORITIES.indexOf(item.priority);

		if (i < dirty) {
			dirty = i;
		}

		queues[i].push(item);
	};

	Deno.bench('buckets', () => {
		for (let i = 0; i < N; i++) {
			push(new Item(RUNNER, PRIORITY_SEQUENCE[i]));
		}

		const offsets = [0, 0, 0];

		rescan: while (dirty < DIRTY_NONE) {
			const i = dirty;
			const queue = queues[i];

			for (let j = offsets[i]; j < queue.length;) {
				(0, queue[j++].runner)();

				if (i !== dirty) {
					offsets[i] = j;
					continue rescan;
				}
			}

			queue.length = 0;
			offsets[i] = 0;
			dirty++;
		}
	});
}