Heap Priority Queue

heap-priority-queue: The Ultimate Cheatsheet

1. Detailed Explanation

What is heap-priority-queue?

A priority queue is an abstract data type similar to a regular queue or stack data structure, but where each element additionally has a “priority” associated with it. In a priority queue, elements are served based on their priority. Elements with higher priority are served before elements with lower priority, regardless of their order of insertion. If elements have the same priority, their order is typically determined by their insertion order (FIFO).

A heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B, then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. This can be either a min-heap, where the key of A is less than or equal to the key of B, or a max-heap, where the key of A is greater than or equal to the key of B.

A heap-priority-queue is an implementation of the priority queue abstract data type using a heap data structure. This provides an efficient way to manage elements with priorities, ensuring that the highest (or lowest) priority element is always readily accessible. Binary heaps are the most common type used for implementing priority queues due to their efficient performance.

Why is it important and what kind of problems does it solve?

Priority queues are crucial for various applications where elements need to be processed in a specific order based on their importance:

• Scheduling: Operating systems use priority queues to schedule tasks based on their priority, ensuring that critical tasks are executed promptly.
• Graph Algorithms: Algorithms like Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm heavily rely on priority queues to efficiently find the next closest node.
• Data Compression: Huffman coding, a popular data compression technique, utilizes priority queues to build the Huffman tree.
• Event Simulation: Simulating events based on their occurrence time often involves using priority queues to process events in chronological order.
• K-related problems: Finding the k-largest, k-smallest, or k-most frequent elements.

Core concepts, underlying principles, and key terminology.

• Priority: A value associated with each element that determines its order in the queue.
• Heap Property: The fundamental rule that dictates the order of elements in a heap (min-heap or max-heap).
• Min-Heap: A heap where the root node has the smallest value, and each node’s value is less than or equal to its children’s values.
• Max-Heap: A heap where the root node has the largest value, and each node’s value is greater than or equal to its children’s values.
• Heapify: The process of rearranging the elements of an array to satisfy the heap property.
• Insert (Push): Adding a new element to the priority queue.
• Extract-Min/Extract-Max (Pop): Removing and returning the element with the highest priority (min or max, depending on the type of heap).
• Peek/Top: Accessing the element with the highest priority without removing it.
• Heap Size: The number of elements currently stored in the heap.

2. When to Use heap-priority-queue (and When Not To)

Identify problem patterns that suggest heap-priority-queue is a good fit.

• Problems involving finding the k-th largest/smallest element.
• Problems requiring elements to be processed in a specific order based on priority.
• Graph algorithms where you need to repeatedly find the node with the smallest/largest distance.
• Situations where you need to maintain a sorted collection of elements and efficiently access the minimum or maximum value.
• Problems involving scheduling tasks based on their priority.

Discuss scenarios where a different data structure or algorithm would be more appropriate.

• If the number of elements is small and performance is not critical: A simple sorted array or list might be sufficient.
• If you need to perform frequent searches for elements other than the minimum or maximum: A balanced binary search tree might be a better choice.
• If the priority values are limited to a small range: A counting sort or bucket sort might be more efficient.
• If you need to maintain the elements in insertion order: A regular queue is more appropriate.
• If all elements have the same priority: A regular queue or stack would suffice.

3. Core Algorithm / Data Structure Template

Here’s a general template for using a heap-priority-queue:

1. Choose Heap Type: Determine whether you need a min-heap (for finding the smallest element) or a max-heap (for finding the largest element).
2. Initialize Heap: Create an empty heap data structure. Many languages provide built-in heap implementations.
3. Insert Elements: Add the elements to the heap, maintaining the heap property after each insertion. This often involves “heapifying” or “sifting up” the newly inserted element.
4. Extract Elements: To retrieve elements in priority order, repeatedly extract the minimum (or maximum) element from the heap. This involves removing the root element and then “heapifying” or “sifting down” the new root element.
5. Peek at Top Element: Access the element with the highest priority (root of the heap) without removing it.

4. Code Implementations (Python, Java, C++)

Python

import heapq

class PriorityQueue:
    def __init__(self, is_min_heap=True):
        self._data = []
        self._is_min_heap = is_min_heap

    def push(self, item, priority):
        # Python's heapq is naturally a min-heap.  To simulate a max-heap, we can store the negative of the priority.
        if self._is_min_heap:
            heapq.heappush(self._data, (priority, item))
        else:
            heapq.heappush(self._data, (-priority, item))  # Negate priority for max-heap simulation

    def pop(self):
        if not self._data:
            return None  # Or raise an exception

        if self._is_min_heap:
            return heapq.heappop(self._data)[1] # return the actual item
        else:
            return heapq.heappop(self._data)[1]

    def peek(self):
        if not self._data:
            return None # Or raise an exception

        if self._is_min_heap:
            return self._data[0][1]
        else:
            return self._data[0][1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
      return len(self._data)


# Example usage
pq = PriorityQueue()  # Min-heap by default
pq.push("Task A", 3)
pq.push("Task B", 1)
pq.push("Task C", 2)

print(pq.pop())  # Output: Task B
print(pq.pop())  # Output: Task C
print(pq.pop())  # Output: Task A

pq_max = PriorityQueue(is_min_heap=False)  # Max-heap
pq_max.push("Task A", 3)
pq_max.push("Task B", 1)
pq_max.push("Task C", 2)

print(pq_max.pop()) # Output: Task A
print(pq_max.pop()) # Output: Task C
print(pq_max.pop()) # Output: Task B

Java

import java.util.PriorityQueue;
import java.util.Comparator;

class PriorityQueueExample {
    public static void main(String[] args) {
        // Min-heap
        PriorityQueue<String> minHeap = new PriorityQueue<>(Comparator.comparingInt(String::length)); // using length as priority
        minHeap.add("apple");
        minHeap.add("banana");
        minHeap.add("kiwi");
        minHeap.add("a");


        System.out.println("Min-Heap:");
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // Output: a, kiwi, apple, banana
        }

        // Max-heap (using a custom comparator)
        PriorityQueue<String> maxHeap = new PriorityQueue<>(Comparator.comparingInt(String::length).reversed());
        maxHeap.add("apple");
        maxHeap.add("banana");
        maxHeap.add("kiwi");
        maxHeap.add("a");

        System.out.println("\nMax-Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // Output: banana, apple, kiwi, a
        }
    }
}

C++

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // Min-heap
    priority_queue<int, vector<int>, greater<int>> minHeap; //Note the comparator for min-heap
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    minHeap.push(9);
    minHeap.push(2);
    minHeap.push(6);

    cout << "Min-Heap:" << endl;
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    // Max-heap (default)
    priority_queue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    maxHeap.push(9);
    maxHeap.push(2);
    maxHeap.push(6);

    cout << "Max-Heap:" << endl;
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;

    return 0;
}

5. Complexity Analysis

Operation	Time Complexity	Space Complexity
Insertion (Push)	O(log n)	O(1)
Extraction (Pop)	O(log n)	O(1)
Peek/Top	O(1)	O(1)
Heapify	O(n)	O(1)

• Best Case: For insertion and extraction, the best case occurs when the element being inserted or extracted maintains the heap property without requiring significant adjustments. This is still O(log n).
• Average Case: The average case for insertion and extraction is O(log n), as elements typically need to be sifted up or down within the heap.
• Worst Case: The worst case for insertion and extraction is O(log n), occurring when the element being inserted or extracted needs to be sifted from the bottom to the root or vice versa. Heapify takes O(n) time.

6. Pro Tips, Tricks, and Common Pitfalls

• Max-Heap Simulation: In languages where only a min-heap is directly available (like Python’s heapq), you can simulate a max-heap by storing the negative of the priority.
• Custom Comparators: Use custom comparators to define the priority based on specific attributes of the elements. This is especially useful when dealing with complex objects.
• Heapify Optimization: When building a heap from an existing array, using the bottom-up heapify approach (starting from the last non-leaf node and working upwards) is more efficient than inserting elements one by one.
• Pitfalls:
  • Incorrect Heap Type: Using the wrong heap type (min-heap vs. max-heap) can lead to incorrect results.
  • Comparator Errors: An incorrect comparator can result in a heap that does not maintain the heap property. Carefully test your comparator.
  • Heap Underflow: Attempting to extract an element from an empty heap can lead to errors. Always check if the heap is empty before extracting.
  • Integer Overflow/Underflow: When using negative priorities to simulate a max-heap, be mindful of potential integer overflow or underflow issues, especially when priorities can be large.
  • Modifying Heap Elements after Insertion: If you modify an element’s priority after it has been inserted into the heap, the heap property might be violated. You may need to re-heapify or remove and re-insert the element.

7. Classic Problem Examples

Example: Kth Largest Element in an Array

Description: Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

High-Level Approach:

1. Use a Min-Heap: Maintain a min-heap of size k.
2. Iterate through the Array:
   • For the first k elements, add them to the min-heap.
   • For the remaining elements, if the current element is greater than the smallest element in the heap (the root of the min-heap), remove the smallest element and add the current element to the heap.
3. Result: After iterating through all the elements, the root of the min-heap will be the kth largest element in the array. This approach has a time complexity of O(N log K), where N is the length of the array and K is the desired element.