Introduction to Priority Queue

Sometimes you need to process items by priority, not just in the order they arrived. That's where priority queues come in. They're like regular queues, but items are processed based on their priority value, not insertion time.

What Is a Priority Queue?

A priority queue is like a regular queue, but items are processed based on priority, not insertion order. Items with higher priority come out first, regardless of when they were added.

Think of it like a hospital emergency room. Critical patients are seen first, not necessarily those who arrived first.

My First Encounter

I was trying to solve a problem about scheduling tasks. I needed to always process the highest priority task next. A regular queue wouldn't work because it's FIFO (First In, First Out). I needed something that could prioritize.

Types of Priority Queues

I learned there are two main types:

Min-Priority Queue: Lower values have higher priority. Like processing the smallest tasks first.

Max-Priority Queue: Higher values have higher priority. Like processing the most urgent tasks first.

Implementation Approaches

I explored three ways to implement priority queues:

1. Using an Array (Simple but Slow)

My first attempt was simple. Just use an array and find the highest priority each time:

class PriorityQueueArray {
  constructor() {
    this.queue = [];
  }

  enqueue(item, priority) {
    this.queue.push({ item, priority });
  }

  dequeue() {
    if (this.isEmpty()) return null;

    // Find highest priority (lowest number for min-priority)
    let highestPriorityIndex = 0;
    for (let i = 1; i < this.queue.length; i++) {
      if (this.queue[i].priority < this.queue[highestPriorityIndex].priority) {
        highestPriorityIndex = i;
      }
    }
    return this.queue.splice(highestPriorityIndex, 1)[0];
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

This worked, but dequeue was O(n) because I had to search for the highest priority. I knew there had to be a better way.

2. Using a Heap (Efficient!)

Then I learned about heaps. A heap is a tree structure where the root is always the min (or max). This makes operations O(log n):

class MinHeap {
  constructor() {
    this.heap = [];
  }

  enqueue(item, priority) {
    this.heap.push({ item, priority });
    this.bubbleUp(); // Maintain heap property
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].priority >= this.heap[parentIndex].priority) break;

      // Swap with parent
      [this.heap[index], this.heap[parentIndex]] = [
        this.heap[parentIndex],
        this.heap[index],
      ];
      index = parentIndex;
    }
  }

  dequeue() {
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0); // Maintain heap property
    return root;
  }

  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];

    while (true) {
      const leftIndex = 2 * index + 1;
      const rightIndex = 2 * index + 2;
      let swapIndex = null;

      // Find smaller child
      if (
        leftIndex < length &&
        this.heap[leftIndex].priority < element.priority
      ) {
        swapIndex = leftIndex;
      }

      if (
        rightIndex < length &&
        this.heap[rightIndex].priority <
          (swapIndex === null
            ? element.priority
            : this.heap[leftIndex].priority)
      ) {
        swapIndex = rightIndex;
      }

      if (swapIndex === null) break;

      [this.heap[index], this.heap[swapIndex]] = [
        this.heap[swapIndex],
        this.heap[index],
      ];
      index = swapIndex;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

This is much better! Both enqueue and dequeue are O(log n).

When I Use Priority Queues

I've found priority queues useful for:

• Dijkstra's algorithm: Finding shortest paths
• Task scheduling: Processing high-priority tasks first
• Event simulation: Processing events in chronological order
• Merge k sorted lists: Always processing the smallest next element

What I Learned

Priority queues taught me:

• Sometimes order matters more than insertion time
• Heaps are the efficient way to implement priority queues
• This data structure appears in many advanced algorithms
• Understanding heaps opens up many optimization opportunities

Key Takeaways

• Priority queues process items by priority, not insertion order
• Heaps provide O(log n) operations for priority queues
• Min-heap for smallest-first, max-heap for largest-first
• This is a fundamental data structure for many algorithms

Learning about priority queues really expanded my problem-solving toolkit. They're one of those structures that, once you understand them, you start seeing opportunities to use them everywhere. I hope this helps you recognize when priority queues can simplify your solutions!