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

README.md

deno bench heap-bench.js

N=10

benchmark	time/iter (avg)	iter/s	(min … max)	p75	p99	p995
heap	141.4 ns	7,070,000	(136.0 ns … 338.0 ns)	142.3 ns	149.0 ns	151.6 ns
redundant sort and shift	1.6 µs	644,800	( 1.5 µs … 1.6 µs)	1.5 µs	1.6 µs	1.6 µs
sort once and pop	421.8 ns	2,371,000	(414.4 ns … 430.1 ns)	424.1 ns	429.4 ns	430.1 ns
buckets	575.0 ns	1,739,000	(568.9 ns … 583.5 ns)	577.4 ns	583.5 ns	583.5 ns

N=400

benchmark	time/iter (avg)	iter/s	(min … max)	p75	p99	p995
heap	11.0 µs	90,830	( 10.2 µs … 530.5 µs)	10.7 µs	15.5 µs	21.0 µs
redundant sort and shift	1.3 ms	751.6	( 1.3 ms … 1.7 ms)	1.3 ms	1.5 ms	1.5 ms
sort once and pop	30.4 µs	32,890	( 28.8 µs … 123.3 µs)	30.3 µs	34.8 µs	39.5 µs
buckets	5.0 µs	200,100	( 4.6 µs … 111.1 µs)	4.8 µs	9.6 µs	12.8 µ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, -1, 0, 10, 16, 100, 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)();
	}
});

// 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 = Array(PRIORITIES.length).fill(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++;
		}
	});
}