Heap / Priority Queue

A heap is a tree-based data structure that maintains the property that the parent is always greater (max-heap) or smaller (min-heap) than its children. It's commonly used as a priority queue.

When to Use

Finding k-th largest/smallest elements
Maintaining a running median
Merging k sorted lists
Problems requiring 'top k' or 'best k' elements

Common Patterns

Top K Elements

Maintain k elements with best values using heap

Example: K closest points, top k frequent elements

Two Heaps

Use max-heap and min-heap together

Example: Find median from data stream

Heap with Custom Comparator

Define custom ordering for complex objects

Example: Meeting rooms, task scheduler

Code Templates

Python

import heapq

# Min heap (default in Python)
min_heap = []
heapq.heappush(min_heap, value)
min_val = heapq.heappop(min_heap)
min_val = min_heap[0]  # Peek without removing

# Max heap (negate values)
max_heap = []
heapq.heappush(max_heap, -value)
max_val = -heapq.heappop(max_heap)

# Heapify existing list
heapq.heapify(list)

# Top K elements pattern
def top_k_elements(nums, k):
    # Use max heap of size k for k smallest
    # Use min heap of size k for k largest
    heap = []
    
    for num in nums:
        heapq.heappush(heap, -num)  # For k largest
        if len(heap) > k:
            heapq.heappop(heap)
    
    return [-x for x in heap]

# Two heaps pattern (median)
class MedianFinder:
    def __init__(self):
        self.small = []  # Max heap (left half)
        self.large = []  # Min heap (right half)
    
    def addNum(self, num):
        heapq.heappush(self.small, -num)
        
        # Balance: ensure small.max <= large.min
        if (self.small and self.large and 
            -self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        # Balance sizes
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)
    
    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

C++

#include <queue>
#include <vector>
using namespace std;

// Min heap (default)
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(value);
int minVal = minHeap.top();
minHeap.pop();

// Max heap
priority_queue<int> maxHeap;
maxHeap.push(value);
int maxVal = maxHeap.top();
maxHeap.pop();

// Custom comparator
auto cmp = [](pair<int,int>& a, pair<int,int>& b) {
    return a.second > b.second;  // Min heap by second
};
priority_queue<pair<int,int>, 
               vector<pair<int,int>>, 
               decltype(cmp)> pq(cmp);

// Top K elements pattern
vector<int> topKElements(vector<int>& nums, int k) {
    priority_queue<int> maxHeap;  // For k largest
    
    for (int num : nums) {
        maxHeap.push(num);
        if (maxHeap.size() > k) {
            maxHeap.pop();
        }
    }
    
    vector<int> result;
    while (!maxHeap.empty()) {
        result.push_back(maxHeap.top());
        maxHeap.pop();
    }
    return result;
}

// Two heaps pattern (median)
class MedianFinder {
private:
    priority_queue<int> small;  // Max heap (left half)
    priority_queue<int, vector<int>, greater<int>> large;  // Min heap
    
public:
    void addNum(int num) {
        small.push(num);
        
        // Balance: ensure small.max <= large.min
        if (!small.empty() && !large.empty() && 
            small.top() > large.top()) {
            large.push(small.top());
            small.pop();
        }
        
        // Balance sizes
        if (small.size() > large.size() + 1) {
            large.push(small.top());
            small.pop();
        }
        if (large.size() > small.size()) {
            small.push(large.top());
            large.pop();
        }
    }
    
    double findMedian() {
        if (small.size() > large.size()) {
            return small.top();
        }
        return (small.top() + large.top()) / 2.0;
    }
};