@@ -1,61 +1,99 @@
+import process from 'node:process';
 import Benchmark, {type Deferred, type Event} from 'benchmark';
 import PQueue from './source/index.js';
+import PriorityQueue from './source/priority-queue.js';
 
 const suite = new Benchmark.Suite() as Benchmark.Suite;
+const smallTaskCount = 100;
+const largeBacklogTaskCount = 10_000;
+const selectedBenchmarks = process.argv.slice(2);
 
 // Benchmark typings aren't up to date, let's help out manually
 type Resolvable = Deferred & {resolve: () => void};
 
-(suite as any)
-	.add('baseline', {
-		defer: true,
+const noop = () => undefined;
 
-		async fn(deferred: Resolvable) {
-			const queue = new PQueue();
+const shouldRunBenchmark = (name: string) => selectedBenchmarks.length === 0
+	|| selectedBenchmarks.some(selectedBenchmark => name.includes(selectedBenchmark));
 
-			for (let i = 0; i < 100; i++) {
-				// eslint-disable-next-line @typescript-eslint/no-empty-function
-				queue.add(async () => {});
-			}
+const addBenchmark = (name: string, fn: () => Promise<void>) => {
+	if (!shouldRunBenchmark(name)) {
+		return;
+	}
 
-			await queue.onEmpty();
-			deferred.resolve();
-		},
-	})
-	.add('operation with random priority', {
+	(suite as any).add(name, {
 		defer: true,
 
 		async fn(deferred: Resolvable) {
-			const queue = new PQueue();
-
-			for (let i = 0; i < 100; i++) {
-				// eslint-disable-next-line @typescript-eslint/no-empty-function
-				queue.add(async () => {}, {
-					priority: Math.trunc(Math.random() * 100),
-				});
-			}
-
-			await queue.onEmpty();
+			await fn();
 			deferred.resolve();
 		},
-	})
-	.add('operation with increasing priority', {
-		defer: true,
+	});
+};
 
-		async fn(deferred: Resolvable) {
-			const queue = new PQueue();
+addBenchmark('baseline', async () => {
+	const queue = new PQueue();
 
-			for (let i = 0; i < 100; i++) {
-				// eslint-disable-next-line @typescript-eslint/no-empty-function
-				queue.add(async () => {}, {
-					priority: i,
-				});
-			}
+	for (let i = 0; i < smallTaskCount; i++) {
+		queue.add(noop);
+	}
 
-			await queue.onEmpty();
-			deferred.resolve();
-		},
-	})
+	await queue.onEmpty();
+});
+
+addBenchmark('operation with random priority', async () => {
+	const queue = new PQueue();
+
+	for (let i = 0; i < smallTaskCount; i++) {
+		queue.add(noop, {
+			priority: Math.trunc(Math.random() * smallTaskCount),
+		});
+	}
+
+	await queue.onEmpty();
+});
+
+addBenchmark('operation with increasing priority', async () => {
+	const queue = new PQueue();
+
+	for (let i = 0; i < smallTaskCount; i++) {
+		queue.add(noop, {
+			priority: i,
+		});
+	}
+
+	await queue.onEmpty();
+});
+
+addBenchmark('large-fifo-backlog', async () => {
+	const queue = new PQueue({autoStart: false});
+
+	for (let i = 0; i < largeBacklogTaskCount; i++) {
+		queue.add(noop);
+	}
+
+	queue.start();
+	await queue.onIdle();
+});
+
+addBenchmark('priority-queue-dequeue', async () => {
+	const queue = new PriorityQueue();
+
+	for (let i = 0; i < largeBacklogTaskCount; i++) {
+		queue.enqueue(noop);
+	}
+
+	let dequeued = 0;
+	while (queue.dequeue() !== undefined) {
+		dequeued++;
+	}
+
+	if (dequeued !== largeBacklogTaskCount) {
+		throw new Error('Dequeued task count mismatch');
+	}
+});
+
+suite
 	.on('cycle', (event: Event) => {
 		console.log(String(event.target as any));
 	})
 
@@ -2,36 +2,50 @@ import {type Queue, type RunFunction} from './queue.js';
 import lowerBound from './lower-bound.js';
 import {type QueueAddOptions} from './options.js';
 
+const compactionThreshold = 100;
+
 export type PriorityQueueOptions = {
 	priority?: number;
 } & QueueAddOptions;
 
 export default class PriorityQueue implements Queue<RunFunction, PriorityQueueOptions> {
 	readonly #queue: Array<PriorityQueueOptions & {run: RunFunction}> = [];
 
+	// Index of the next item to dequeue. Old items are compacted lazily so dequeue stays O(1).
+	#head = 0;
+
 	enqueue(run: RunFunction, options?: Partial<PriorityQueueOptions>): void {
 		const {
 			priority = 0,
 			id,
 		} = options ?? {};
 
+		const {size} = this;
 		const element = {
 			priority,
 			id,
 			run,
 		};
 
-		if (this.size === 0 || this.#queue[this.size - 1]!.priority! >= priority) {
+		if (size === 0) {
+			this.#queue.length = 0;
+			this.#head = 0;
+			this.#queue.push(element);
+			return;
+		}
+
+		if (this.#queue.at(-1)!.priority! >= priority) {
 			this.#queue.push(element);
 			return;
 		}
 
+		this.#compact();
 		const index = lowerBound(this.#queue, element, (a: Readonly<PriorityQueueOptions>, b: Readonly<PriorityQueueOptions>) => b.priority! - a.priority!);
 		this.#queue.splice(index, 0, element);
 	}
 
 	setPriority(id: string, priority: number) {
-		const index: number = this.#queue.findIndex((element: Readonly<PriorityQueueOptions>) => element.id === id);
+		const index = this.#queue.findIndex((element: Readonly<PriorityQueueOptions>, index) => index >= this.#head && element.id === id);
 		if (index === -1) {
 			throw new ReferenceError(`No promise function with the id "${id}" exists in the queue.`);
 		}
@@ -43,7 +57,11 @@ export default class PriorityQueue implements Queue<RunFunction, PriorityQueueOp
 	remove(id: string): void;
 	remove(run: RunFunction): void;
 	remove(idOrRun: string | RunFunction): void {
-		const index = this.#queue.findIndex((element: Readonly<PriorityQueueOptions & {run: RunFunction}>) => {
+		const index = this.#queue.findIndex((element: Readonly<PriorityQueueOptions & {run: RunFunction}>, index) => {
+			if (index < this.#head) {
+				return false;
+			}
+
 			if (typeof idOrRun === 'string') {
 				return element.id === idOrRun;
 			}
@@ -57,15 +75,46 @@ export default class PriorityQueue implements Queue<RunFunction, PriorityQueueOp
 	}
 
 	dequeue(): RunFunction | undefined {
-		const item = this.#queue.shift();
+		if (this.#head === this.#queue.length) {
+			return undefined;
+		}
+
+		const item = this.#queue[this.#head];
+		this.#head++;
+
+		if (this.#head === this.#queue.length) {
+			this.#queue.length = 0;
+			this.#head = 0;
+		} else if (this.#head > compactionThreshold && this.#head > this.#queue.length / 2) {
+			this.#compact();
+		}
+
 		return item?.run;
 	}
 
 	filter(options: Readonly<Partial<PriorityQueueOptions>>): RunFunction[] {
-		return this.#queue.filter((element: Readonly<PriorityQueueOptions>) => element.priority === options.priority).map((element: Readonly<{run: RunFunction}>) => element.run);
+		const result: RunFunction[] = [];
+
+		for (let index = this.#head; index < this.#queue.length; index++) {
+			const element = this.#queue[index]!;
+			if (element.priority === options.priority) {
+				result.push(element.run);
+			}
+		}
+
+		return result;
 	}
 
 	get size(): number {
-		return this.#queue.length;
+		return this.#queue.length - this.#head;
+	}
+
+	#compact(): void {
+		if (this.#head === 0) {
+			return;
+		}
+
+		this.#queue.splice(0, this.#head);
+		this.#head = 0;
 	}
 }
@@ -0,0 +1,130 @@
+import {test} from 'node:test';
+import assert from 'node:assert/strict';
+import PriorityQueue from '../source/priority-queue.js';
+
+const createRun = (value: string) => async () => value;
+
+test('PriorityQueue ignores dequeued items in queue operations', () => {
+	const queue = new PriorityQueue();
+	const first = createRun('first');
+	const second = createRun('second');
+	const third = createRun('third');
+
+	queue.enqueue(first, {id: 'same', priority: 0});
+	queue.enqueue(second, {id: 'same', priority: 0});
+	queue.enqueue(third, {id: 'third', priority: 0});
+
+	assert.equal(queue.dequeue(), first);
+	assert.deepEqual(queue.filter({priority: 0}), [second, third]);
+
+	queue.setPriority('same', 2);
+	queue.remove(third);
+
+	assert.equal(queue.size, 1);
+	assert.equal(queue.dequeue(), second);
+	assert.equal(queue.dequeue(), undefined);
+});
+
+test('PriorityQueue inserts high-priority items correctly after partial dequeue', () => {
+	const queue = new PriorityQueue();
+	const first = createRun('first');
+	const second = createRun('second');
+	const third = createRun('third');
+	const urgent = createRun('urgent');
+
+	queue.enqueue(first, {priority: 0});
+	queue.enqueue(second, {priority: 0});
+	queue.enqueue(third, {priority: -1});
+
+	assert.equal(queue.dequeue(), first);
+
+	queue.enqueue(urgent, {priority: 1});
+
+	assert.equal(queue.size, 3);
+	assert.equal(queue.dequeue(), urgent);
+	assert.equal(queue.dequeue(), second);
+	assert.equal(queue.dequeue(), third);
+	assert.equal(queue.dequeue(), undefined);
+});
+
+test('PriorityQueue removes the live duplicate id after partial dequeue', () => {
+	const queue = new PriorityQueue();
+	const first = createRun('first');
+	const second = createRun('second');
+	const third = createRun('third');
+
+	queue.enqueue(first, {id: 'same'});
+	queue.enqueue(second, {id: 'same'});
+	queue.enqueue(third, {id: 'third'});
+
+	assert.equal(queue.dequeue(), first);
+
+	queue.remove('same');
+
+	assert.equal(queue.size, 1);
+	assert.equal(queue.dequeue(), third);
+	assert.equal(queue.dequeue(), undefined);
+});
+
+test('PriorityQueue removes by run after partial dequeue', () => {
+	const queue = new PriorityQueue();
+	const first = createRun('first');
+	const second = createRun('second');
+	const third = createRun('third');
+
+	queue.enqueue(first);
+	queue.enqueue(second);
+	queue.enqueue(third);
+
+	assert.equal(queue.dequeue(), first);
+
+	queue.remove(second);
+
+	assert.equal(queue.size, 1);
+	assert.equal(queue.dequeue(), third);
+	assert.equal(queue.dequeue(), undefined);
+});
+
+test('PriorityQueue stays ordered after cursor compaction', () => {
+	const queue = new PriorityQueue();
+	const urgent = createRun('urgent');
+
+	for (let index = 0; index < 150; index++) {
+		queue.enqueue(createRun(`task-${index}`));
+	}
+
+	// Cross the compaction threshold while leaving queued items behind.
+	for (let index = 0; index < 120; index++) {
+		assert.notEqual(queue.dequeue(), undefined);
+	}
+
+	queue.enqueue(urgent, {priority: 1});
+
+	assert.equal(queue.size, 31);
+	assert.equal(queue.dequeue(), urgent);
+
+	let remaining = 0;
+	while (queue.dequeue() !== undefined) {
+		remaining++;
+	}
+
+	assert.equal(remaining, 30);
+	assert.equal(queue.size, 0);
+});
+
+test('PriorityQueue setPriority works when only one live item remains', () => {
+	const queue = new PriorityQueue();
+	const first = createRun('first');
+	const second = createRun('second');
+
+	queue.enqueue(first, {id: 'first'});
+	queue.enqueue(second, {id: 'second'});
+
+	assert.equal(queue.dequeue(), first);
+
+	queue.setPriority('second', 1);
+
+	assert.equal(queue.size, 1);
+	assert.equal(queue.dequeue(), second);
+	assert.equal(queue.dequeue(), undefined);
+});