Priority Queue (Heap)

Generated on 2025-07-10 02:09:35 Algorithm Cheatsheet for Technical Interviews

---

Priority Queue (Heap) Cheatsheet

1. Quick Overview

• What: A priority queue is an abstract data type that behaves like a queue, but each element has an associated priority. Elements are dequeued based on their priority (highest priority first). Heaps are a common implementation of priority queues.
• When to Use:
  • Finding the smallest/largest element repeatedly.
  • Implementing Dijkstra’s algorithm, A* search.
  • Task scheduling based on priority.
  • Merging sorted lists.
  • Event-driven simulations.
  • Heap sort.

2. Time & Space Complexity

Operation	Time Complexity	Space Complexity
insert / push	O(log n)	O(1)
get_min / get_max	O(1)	O(1)
extract_min / extract_max	O(log n)	O(1)
peek	O(1)	O(1)
size	O(1)	O(1)
build_heap	O(n)	O(1)

• n represents the number of elements in the heap.

3. Implementation

Python:

import heapq

# Min Heap
class MinHeap:
    def __init__(self, items=None):
        self.heap = items if items else []
        if items:
            heapq.heapify(self.heap) # O(n)

    def push(self, item):
        heapq.heappush(self.heap, item)  # O(log n)

    def pop(self):
        return heapq.heappop(self.heap)   # O(log n)

    def peek(self):
        return self.heap[0] if self.heap else None # O(1)

    def size(self):
        return len(self.heap) # O(1)

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

# Max Heap (using negative values)
class MaxHeap:
    def __init__(self, items=None):
        self.heap = [-x for x in items] if items else []
        if items:
            heapq.heapify(self.heap)

    def push(self, item):
        heapq.heappush(self.heap, -item)

    def pop(self):
        return -heapq.heappop(self.heap)

    def peek(self):
        return -self.heap[0] if self.heap else None

    def size(self):
        return len(self.heap)

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

# Example
min_heap = MinHeap([3, 1, 4, 1, 5, 9, 2, 6])
print("Min Heap:", min_heap.heap)  # Output: [1, 1, 2, 3, 5, 9, 4, 6]
print("Min:", min_heap.pop())       # Output: 1

max_heap = MaxHeap([3, 1, 4, 1, 5, 9, 2, 6])
print("Max Heap:", max_heap.heap)
print("Max:", max_heap.pop())       # Output: 9

Java:

import java.util.PriorityQueue;
import java.util.Collections;

public class HeapExample {
    public static void main(String[] args) {
        // Min Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(4);
        minHeap.add(1);
        minHeap.add(5);
        minHeap.add(9);
        minHeap.add(2);
        minHeap.add(6);

        System.out.println("Min Heap: " + minHeap); // Order isn't guaranteed until polled
        System.out.println("Min: " + minHeap.poll()); // Output: 1

        // Max Heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(3);
        maxHeap.add(1);
        maxHeap.add(4);
        maxHeap.add(1);
        maxHeap.add(5);
        maxHeap.add(9);
        maxHeap.add(2);
        maxHeap.add(6);

        System.out.println("Max Heap: " + maxHeap);
        System.out.println("Max: " + maxHeap.poll()); // Output: 9
    }
}

C++:

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

int main() {
    // Min Heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    minHeap.push(9);
    minHeap.push(2);
    minHeap.push(6);

    std::cout << "Min: " << minHeap.top() << std::endl; // Output: 1
    minHeap.pop();

    // Max Heap
    std::priority_queue<int> maxHeap; // Default is max heap
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    maxHeap.push(9);
    maxHeap.push(2);
    maxHeap.push(6);

    std::cout << "Max: " << maxHeap.top() << std::endl; // Output: 9
    maxHeap.pop();

    return 0;
}

4. Common Patterns

• Kth Largest/Smallest Element: Use a min-heap for kth largest or a max-heap for kth smallest. Maintain a heap of size k.
• Merging Sorted Lists: Use a min-heap to store the smallest element from each list. Each time you extract the smallest, add the next element from its original list.
• Dijkstra’s Algorithm: Use a min-heap to store vertices based on their distance from the source.
• Median Finding: Use two heaps: a max-heap for the smaller half of the data and a min-heap for the larger half. Balance the heaps to keep them roughly the same size.
• Sliding Window Maximum: Use a deque or a priority queue to track the maximum element within a sliding window of size k.

5. Pro Tips

• Heapify (O(n)): Use the heapify function (available in most libraries) to build a heap from an existing array in O(n) time. Don’t repeatedly insert elements into an empty heap - it’s much slower (O(n log n)).
• Max Heap with Min Heap Implementation: Use negative values to simulate a max-heap using a min-heap implementation. Remember to negate when pushing and popping.
• Custom Objects: When using heaps with custom objects, ensure that the objects are comparable (implement Comparable in Java, overload comparison operators in C++, or provide a key function in Python’s heapq).
• Heap Size: Be mindful of the heap size. For problems involving potentially unbounded input, consider using a fixed-size heap to maintain only the k largest/smallest elements.
• Lazy Deletion: Instead of physically removing elements from the heap (which is difficult), mark them as “deleted” and ignore them when they are popped. This can simplify certain algorithms.

6. Practice Problems

1. Kth Largest Element in a Stream (LeetCode 703): Design a class to find the kth largest element in a stream.

   • Solution: Use a min-heap of size k to store the k largest elements seen so far. The root of the heap will always be the kth largest.

2. Merge k Sorted Lists (LeetCode 23): Merge k sorted linked lists into one sorted linked list.

   • Solution: Use a min-heap to store the head nodes of each list. Each time you extract the smallest, add the next node from its original list.

3. Dijkstra’s Algorithm (Implementation): Implement Dijkstra’s algorithm to find the shortest path from a source node to all other nodes in a graph.

   • Solution: Use a min-heap to store nodes based on their distance from the source. Update distances as you explore the graph.

7. Templates

C++

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

// Min Heap Template
template <typename T>
class MinHeap {
public:
    MinHeap() {}

    void push(const T& val) {
        pq.push(val);
    }

    T top() const {
        return pq.top();
    }

    void pop() {
        pq.pop();
    }

    bool empty() const {
        return pq.empty();
    }

    size_t size() const {
        return pq.size();
    }

private:
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
};


// Max Heap Template
template <typename T>
class MaxHeap {
public:
    MaxHeap() {}

    void push(const T& val) {
        pq.push(val);
    }

    T top() const {
        return pq.top();
    }

    void pop() {
        pq.pop();
    }

    bool empty() const {
        return pq.empty();
    }

    size_t size() const {
        return pq.size();
    }

private:
    std::priority_queue<T> pq;
};

int main() {
    MinHeap<int> minHeap;
    minHeap.push(5);
    minHeap.push(2);
    minHeap.push(8);
    std::cout << "Min Heap top: " << minHeap.top() << std::endl; // Output: 2

    MaxHeap<int> maxHeap;
    maxHeap.push(5);
    maxHeap.push(2);
    maxHeap.push(8);
    std::cout << "Max Heap top: " << maxHeap.top() << std::endl; // Output: 8

    return 0;
}

Python

import heapq

# Min Heap Template
class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0] if self.heap else None

    def size(self):
        return len(self.heap)

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

# Max Heap Template (using negative values)
class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, item):
        heapq.heappush(self.heap, -item)

    def pop(self):
        return -heapq.heappop(self.heap)

    def peek(self):
        return -self.heap[0] if self.heap else None

    def size(self):
        return len(self.heap)

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

# Example
if __name__ == "__main__":
    min_heap = MinHeap()
    min_heap.push(3)
    min_heap.push(1)
    min_heap.push(2)
    print("Min Heap:", min_heap.heap)
    print("Min:", min_heap.pop())

    max_heap = MaxHeap()
    max_heap.push(3)
    max_heap.push(1)
    max_heap.push(2)
    print("Max Heap:", max_heap.heap)
    print("Max:", max_heap.pop())

Java

import java.util.PriorityQueue;
import java.util.Collections;

// Min Heap Template
class MinHeap<T extends Comparable<T>> {
    private PriorityQueue<T> pq;

    public MinHeap() {
        pq = new PriorityQueue<>();
    }

    public void push(T val) {
        pq.offer(val);
    }

    public T top() {
        return pq.peek();
    }

    public T pop() {
        return pq.poll();
    }

    public boolean empty() {
        return pq.isEmpty();
    }

    public int size() {
        return pq.size();
    }
}


// Max Heap Template
class MaxHeap<T extends Comparable<T>> {
    private PriorityQueue<T> pq;

    public MaxHeap() {
        pq = new PriorityQueue<>(Collections.reverseOrder());
    }

    public void push(T val) {
        pq.offer(val);
    }

    public T top() {
        return pq.peek();
    }

    public T pop() {
        return pq.poll();
    }

    public boolean empty() {
        return pq.isEmpty();
    }

    public int size() {
        return pq.size();
    }
}

public class HeapTemplates {
    public static void main(String[] args) {
        MinHeap<Integer> minHeap = new MinHeap<>();
        minHeap.push(5);
        minHeap.push(2);
        minHeap.push(8);
        System.out.println("Min Heap top: " + minHeap.top()); // Output: 2

        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        maxHeap.push(5);
        maxHeap.push(2);
        maxHeap.push(8);
        System.out.println("Max Heap top: " + maxHeap.top()); // Output: 8
    }
}