Heap-based Priority Queues

1. What is a Priority Queue?

A standard queue operates on a "first-in, first-out" (FIFO) principle. A Priority Queue (PQ) is different: it's an abstract data type where each element has an associated "priority." When you extract an element, you always get the one with the highest priority, regardless of when it was added.

• In a min-priority queue, the element with the lowest value has the highest priority.
• In a max-priority queue, the element with the highest value has the highest priority.

This concept appears everywhere:

• Operating Systems: Scheduling processes based on their priority level.
• Networking: Routing data packets that have urgent flags.
• AI: In algorithms like A* search, a priority queue is used to explore the most promising paths first.

The main operations of a priority queue are:

1. Insert/Enqueue: Add a new element to the queue.
2. Extract-Highest-Priority/Dequeue: Remove and return the element with the highest priority.
3. Peek: Look at the highest-priority element without removing it.

The critical question for an interview is: what's the most efficient way to build this?

2. Why a Heap is the Ideal Implementation

Let's consider other data structures you know. How would they perform as a priority queue?

• Unsorted Array/List: Insertion is $O(1)$. But to find the highest-priority item, you must search the entire list, which takes $O(N)$ time.
• Sorted Array/List: Finding the highest-priority item is $O(1)$ (it's at one of the ends). However, inserting an element while keeping the array sorted requires shifting elements, which takes $O(N)$ time.

Neither of these is ideal. We want our operations to be faster. This is where heaps shine. To understand the motivation better, let's watch a video that frames this problem perfectly.

As the video argues, a heap provides the perfect balance:

• Peek: $O(1)$, because the highest-priority element is always the root.
• Insert: $O(\log N)$.
• Extract: $O(\log N)$.

This is a massive improvement over the $O(N)$ complexities of the array-based approaches.

3. Implementing a Priority Queue with Our Heap

Let's now complete the MinHeap class we started in the previous lesson to make it a fully functional min-priority queue. We'll add the public-facing push (insert) and pop (extract-min) methods that use the _sift_up and _sift_down helpers you've already learned.

# Building on the class from the previous lesson
class MinPriorityQueue:
    def __init__(self):
        # The heap is stored as a list (dynamic array)
        self.heap = []

    def push(self, val):
        """Adds an element to the priority queue. O(log N)"""
        # 1. Add the element to the end to maintain the 'complete tree' shape.
        self.heap.append(val)
        # 2. Sift it up to restore the heap property.
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        """Removes and returns the element with the highest priority (the minimum). O(log N)"""
        if not self.heap:
            return None
        
        # 1. The root is the min element we need to return.
        min_val = self.heap[0]
        
        # 2. To fill the hole at the root, move the last element there.
        last_val = self.heap.pop() # Removes and returns the last element
        
        # If there are still elements left after popping...
        if self.heap:
            self.heap[0] = last_val
            # 3. Sift the new root down to restore the heap property.
            self._sift_down(0)
            
        return min_val

    def peek(self):
        """Returns the smallest element without removing it. O(1)"""
        return self.heap[0] if self.heap else None

    # --- Helper methods from the previous lesson ---

    def _parent_index(self, i):
        return (i - 1) // 2

    def _sift_up(self, i):
        # Iterative implementation is common in interviews
        parent_idx = self._parent_index(i)
        while i > 0 and self.heap[i] < self.heap[parent_idx]:
            self.heap[i], self.heap[parent_idx] = self.heap[parent_idx], self.heap[i]
            i = parent_idx
            parent_idx = self._parent_index(i)

    def _sift_down(self, i):
        while True:
            smallest = i
            left_child_idx = 2 * i + 1
            right_child_idx = 2 * i + 2

            if left_child_idx < len(self.heap) and self.heap[left_child_idx] < self.heap[smallest]:
                smallest = left_child_idx
            
            if right_child_idx < len(self.heap) and self.heap[right_child_idx] < self.heap[smallest]:
                smallest = right_child_idx

            if smallest != i:
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                i = smallest
            else:
                break # The heap property is restored for this subtree

This class is now a complete implementation of a min-priority queue. To see a slightly different but equally valid implementation and review the core logic, you can study the following resource.

4. Priority Queues in Standard Libraries

While knowing how to build a PQ from scratch is vital for demonstrating deep understanding in an interview, you'll almost always use a built-in library for actual problem-solving.

Python: The heapq Module

Python's standard library provides the heapq module, which implements a min-heap. You use it directly on a standard Python list.

A key interview trick is to implement a max-heap using heapq. Since heapq is a min-heap, it always keeps the smallest element at the top. To simulate a max-heap, you can simply insert the negation of your numbers. The smallest negative number will correspond to the largest positive number.

The following resource gives a practical guide to using heapq for both min- and max-priority queues.

Java: The PriorityQueue Class

For your Java proficiency, it's good to know that Java has a PriorityQueue class built-in.

By default, it's a min-priority queue. To make it a max-priority queue, you provide a Comparator that reverses the natural ordering. For example: new PriorityQueue<>(Collections.reverseOrder()); or new PriorityQueue<>((a, b) -> b - a);.

Conclusion

You've successfully connected the low-level heap mechanics to the high-level concept of a priority queue. This is a critical link to understand for solving a wide range of algorithmic problems.

Key Takeaways:

• A Priority Queue is an abstract data type that serves elements based on priority, not insertion order.
• A heap is the most efficient data structure for implementing a priority queue, offering $O(\log N)$ for insertions and extractions, and $O(1)$ for peeking.
• The heap's sift-up and sift-down operations are the engines that power the priority queue's push and pop methods.
• For interviews, you should be familiar with both the from-scratch implementation and the standard library versions like Python's heapq and Java's PriorityQueue.

In our next lesson, we will apply what we've learned to a classic and very common interview pattern: solving "Top K" element problems using heaps. You'll see just how powerful this data structure can be.