Priority Queues in DSA: Heap-Based Implementations

Core Principles:

• Element Priority: Highest/lowest priority served first
• Key Operations: Insert, Extract-Max/Min, Peek
• Underlying Structure: Typically implemented with heaps

Time Complexities:

* Amortized time

Binary Heap Implementation:

class MinHeap {
  constructor() {
    this.heap = [];
  }
  
  insert(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  extractMin() {
    if (this.isEmpty()) throw new Error("Heap is empty");
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return min;
  }
  
  bubbleUp(index) {
    while (index > 0) {
      const parentIdx = Math.floor((index - 1) / 2);
      if (this.heap[parentIdx] <= this.heap[index]) break;
      [this.heap[parentIdx], this.heap[index]] = 
        [this.heap[index], this.heap[parentIdx]];
      index = parentIdx;
    }
  }
  
  sinkDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;
    
    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }
    
    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }
    
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = 
        [this.heap[smallest], this.heap[index]];
      this.sinkDown(smallest);
    }
  }
}

Classic Algorithms:

function dijkstra(graph, start) {
  const distances = {};
  const pq = new MinHeap();
  const visited = new Set();
  
  // Initialize distances
  for (const vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    pq.insert({ vertex, distance: distances[vertex] });
  }
  
  while (!pq.isEmpty()) {
    const { vertex: current, distance } = pq.extractMin();
    if (visited.has(current)) continue;
    visited.add(current);
    
    for (const neighbor in graph[current]) {
      const newDistance = distance + graph[current][neighbor];
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        pq.insert({ vertex: neighbor, distance: newDistance });
      }
    }
  }
  
  return distances;
}

class HuffmanNode {
  constructor(char = null, freq = 0, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

function buildHuffmanTree(freqMap) {
  const pq = new MinHeap(
    (a, b) => a.freq < b.freq
  );
  
  // Create leaf nodes for each character
  for (const [char, freq] of Object.entries(freqMap)) {
    pq.insert(new HuffmanNode(char, freq));
  }
  
  // Build the tree
  while (pq.size() > 1) {
    const left = pq.extractMin();
    const right = pq.extractMin();
    const merged = new HuffmanNode(null, left.freq + right.freq, left, right);
    pq.insert(merged);
  }
  
  return pq.extractMin();
}

Real-world Use Cases:

• Hospital Triage: Prioritize patients by severity
• Network Routing: Prioritize data packets
• Job Scheduling: OS process prioritization
• Load Balancing: Prioritize server requests

Optimization Patterns:

// Build heap in O(n) time instead of O(n log n)
function heapify(arr) {
  const start = Math.floor(arr.length / 2) - 1;
  for (let i = start; i >= 0; i--) {
    sinkDown(arr, i, arr.length);
  }
  return arr;
}

function sinkDown(arr, index, length) {
  let largest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;
  
  if (left < length && arr[left] > arr[largest]) {
    largest = left;
  }
  
  if (right < length && arr[right] > arr[largest]) {
    largest = right;
  }
  
  if (largest !== index) {
    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    sinkDown(arr, largest, length);
  }
}

function mergeKSortedArrays(arrays) {
  const pq = new MinHeap(
    (a, b) => a.value < b.value
  );
  const result = [];
  
  // Initialize heap with first element of each array
  for (let i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) {
      pq.insert({ 
        value: arrays[i][0], 
        arrayIndex: i, 
        elementIndex: 0 
      });
    }
  }
  
  while (!pq.isEmpty()) {
    const { value, arrayIndex, elementIndex } = pq.extractMin();
    result.push(value);
    
    if (elementIndex + 1 < arrays[arrayIndex].length) {
      pq.insert({
        value: arrays[arrayIndex][elementIndex + 1],
        arrayIndex,
        elementIndex: elementIndex + 1
      });
    }
  }
  
  return result;
}