Binary Heaps: Implementing a Priority Queue

1. What is a Priority Queue?

A standard queue follows a "First-In, First-Out" (FIFO) principle. A priority queue, on the other hand, is a collection of items where each item has an associated priority. When you dequeue an item, you don't get the one that was added first; you get the one with the highest priority.

The main operations of a priority queue are:

• enqueue(item, priority): Adds an item to the queue.
• dequeue(): Removes and returns the item with the highest priority.
• peek(): Returns the highest-priority item without removing it.

As a developer, you can think of the priority queue as an API or an interface. The question then becomes: what is the most efficient data structure to use for its internal implementation?

2. Why a Binary Heap is the Ideal Implementation

Let's consider a few data structures you already know and analyze their suitability for implementing a priority queue. Let's assume we want to find the element with the highest priority.

The binary heap provides the best trade-off, ensuring that both adding and removing elements are consistently fast, even in the worst case.

The mapping from priority queue operations to heap operations (using a max-heap for a highest-priority-first queue) is remarkably direct:

• enqueue(item) maps to heap.insert(item).
• dequeue() maps to heap.extractMax().
• peek() maps to heap.getMax() (i.e., accessing the root at index 0, which is O(1)).

The following video provides a clear, visual explanation of how to use the heap class you built previously to create a priority queue.

3. Implementing the Priority Queue

Now, let's put this into practice. A key principle in software architecture is composition over inheritance. Instead of making our PriorityQueue a type of Heap, we will design our PriorityQueue class to contain a Heap instance. This decouples the PriorityQueue's public API from its internal implementation, making the design cleaner and more flexible.

First, let's assume we have the MaxHeap class from the previous lesson. Its interface would look something like this (we'll omit the internal implementation for brevity):

// From the previous lesson...
class MaxHeap {
    constructor() { /* ... */ }
    insert(value) { /* ... O(log n) logic ... */ }
    extractMax() { /* ... O(log n) logic ... */ }
    peek() { /* ... O(1) logic ... */ }
    size() { /* ... O(1) logic ... */ }
}

Now, we can build our PriorityQueue class by composing it with MaxHeap.

Simple Implementation (Priorities are Numbers)

In the simplest case, the items themselves are numbers that represent their own priority.

class PriorityQueue {
    constructor() {
        // The PriorityQueue has a MaxHeap to manage its data.
        this.heap = new MaxHeap();
    }

    // Add an item (its value is its priority)
    enqueue(item) {
        this.heap.insert(item);
    }

    // Remove and return the highest-priority item
    dequeue() {
        return this.heap.extractMax();
    }

    // Look at the highest-priority item
    peek() {
        return this.heap.peek();
    }

    // Check if the queue is empty
    isEmpty() {
        return this.heap.size() === 0;
    }

    // Get the number of items
    size() {
        return this.heap.size();
    }
}

As you can see, the PriorityQueue class is a thin wrapper. It delegates all the hard work to the heap, providing a clean, abstract interface to the user.

Advanced Implementation (Items with Separate Priorities)

In most real-world scenarios, you'll be managing objects where the priority is just one of several properties. For example: { task: 'Process video', priority: 100 }.

To handle this, you need to make a small adjustment to your heap implementation: the comparison logic must be told to compare items based on their priority property.

Here's how the siftUp logic in your MaxHeap class might change:

// Inside MaxHeap class...
siftUp(i) {
    let p = this.parent(i);
    // Compare the 'priority' property of the objects
    while (i > 0 && this.arr[i].priority > this.arr[p].priority) {
        [this.arr[i], this.arr[p]] = [this.arr[p], this.arr[i]];
        i = p;
        p = this.parent(i);
    }
}

The siftDown method would require a similar change. With this modification, your PriorityQueue can now enqueue({ task: '...', priority: ... }) and the heap will correctly order them.

The following resource provides full code examples for a priority queue built on a binary heap. While it doesn't use a separate Heap class, you can see the same logic in action.

Conclusion

In this lesson, you've bridged the gap between a data structure (the binary heap) and an abstract data type (the priority queue). This is a perfect example of the "architectural thinking" you're aiming for: choosing the right tool for the job to build efficient and clean systems.

Key Takeaways:

• A Priority Queue is an abstract data type that serves items based on priority, not insertion order.
• A Binary Heap is the most common and efficient data structure for implementing a priority queue, offering reliable O(log n) performance for enqueue and dequeue operations.
• The implementation involves creating a PriorityQueue class that composes a Heap instance, delegating the core logic to the heap's insert and extractMax methods.
• For real-world use, the heap's comparison logic can be adapted to handle objects with distinct priority fields.

Preview of the next lesson:
Now that you have a fully functional priority queue, what can you do with it? In the next lesson, we will apply the priority queue to solve a classic selection problem: finding the "k-th largest element" in a stream of data. This will demonstrate the practical power of the data structure you've just built.