PriorityQueue

The PriorityQueue<T> class is a generic priority queue implementation in TypeScript, supporting custom comparison functions for prioritization. Commonly used for things like path finding. For example in A* algorithm

Class Definition

export default class PriorityQueue<T> {
  private heap: { value: T; priority: number }[];
  private compare: (a: T, b: T) => number;

  constructor(compareFn: (a: T, b: T) => number);

  enqueue(value: T, priority: number): void;
  dequeue(): T;
  isEmpty(): boolean;
}

Methods

constructor(compareFn: (a: T, b: T) => number)

Creates a new priority queue with a custom comparison function.

enqueue(value: T, priority: number): void

Adds an element with a given priority to the queue and maintains heap order.

dequeue(): T

Removes and returns the element with the highest priority (smallest priority number). Throws an error if the queue is empty.

isEmpty(): boolean

Returns true if the queue is empty, otherwise false.

Internal Methods

private bubbleUp(): void

Ensures heap order by moving a newly inserted element up if necessary.

private bubbleDown(): void

Ensures heap order by moving the root element down after a removal.

Usage Example

const pq = new PriorityQueue<number>((a, b) => a - b);
pq.enqueue(5, 2);
pq.enqueue(1, 1);
pq.enqueue(10, 3);

console.log(pq.dequeue()); // 1
console.log(pq.isEmpty()); // false