Priority Queue

Process items by priority, not arrival order. Used in task scheduling, event simulation, and graph algorithms.

class PriorityQueue {
  private items: { value: any; priority: number }[];

  constructor() {
    this.items = [];
  }

  // Add item with priority
  enqueue(value: any, priority: number): void {
    this.items.push({ value, priority });
    this.bubbleUp(this.items.length - 1);
  }

  // Remove and return highest priority item
  dequeue(): any | undefined {
    if (this.items.length === 0) return undefined;
    if (this.items.length === 1) return this.items.pop()!.value;

    const min = this.items[0]!.value;
    this.items[0] = this.items.pop() as { value: any; priority: number };
    this.bubbleDown(0);
    return min;
  }

  // Helper: bubble up to maintain heap property
  private bubbleUp(index: number): void {
    const parent = Math.floor((index - 1) / 2);
    if (index > 0 && this.items[index]!.priority < this.items[parent]!.priority) {
      if (this.items[index] && this.items[parent]) {
        [this.items[index], this.items[parent]] = [this.items[parent], this.items[index]];
      }
      this.bubbleUp(parent);
    }
  }

  // Helper: bubble down to maintain heap property
  private bubbleDown(index: number): void {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

    if (left < this.items.length && this.items[left]!.priority < this.items[smallest]!.priority) {
      smallest = left;
    }
    if (right < this.items.length && this.items[right]!.priority < this.items[smallest]!.priority) {
      smallest = right;
    }

    if (smallest !== index) {
      [this.items[index]!, this.items[smallest]!] = [this.items[smallest]!, this.items[index]!];
      this.bubbleDown(smallest);
    }
  }
}

const pq = new PriorityQueue();
pq.enqueue("low priority task", 3);
pq.enqueue("urgent task", 1);
pq.enqueue("medium task", 2);
console.log(pq.dequeue()); // "urgent task" (lowest priority number = highest priority)
console.log(pq.dequeue()); // "medium task"

---