LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Greedy Algorithm/Greedy with Priority Queue: Pattern, Template, and When to Use It

Greedy with Priority Queue: Pattern, Template, and When to Use It

LeetCopilot Team
Dec 30, 2025
10 min read
Greedy AlgorithmPriority QueueHeapDynamic SelectionInterview Prep
Learn when and how to combine greedy with priority queues. Master the pattern for dynamic optimal selection with complete templates and examples.
Complete Guide

The Complete Greedy Algorithm Guide: Master All Patterns, Proofs, and Recognition Techniques

The ultimate comprehensive guide to greedy algorithms. Learn all patterns (interval scheduling, sorting, state tracking), when to use greedy vs DP, complete templates in multiple languages, proof techniques, and a systematic approach to solve any greedy problem.

Read the complete guide

Some greedy problems require dynamically selecting the optimal element as you add or remove items. This is where priority queues (heaps) come in.

This guide teaches you when to combine greedy with heaps, the universal template, and key examples.

TL;DR

Use greedy + priority queue when:

  • Need to dynamically select optimal element
  • Adding/removing items while maintaining optimal
  • "Select k best" with changing candidates

Template: Sort by criterion, use heap to track k best, greedy selection based on heap top.

Time: O(n log n) for sort + O(n log k) for heap operations

When to Combine Greedy with Priority Queue

The Pattern

Problem type: Select k elements optimally while candidates change dynamically.

Why heap? Heap gives O(log n) access to min/max, enabling greedy decisions as the candidate set changes.

Key insight: When you need to maintain "the best k elements so far" or "the next optimal choice" as you process items in a specific order, a heap is your tool.

Examples:

  • Minimum Cost to Hire K Workers (LC #857)
  • Meeting Rooms II (LC #253)
  • IPO (LC #502)
  • Task Scheduler (LC #621)

The Core Idea

The greedy + heap pattern works when:

  1. There's a greedy ordering (sort by some criterion)
  2. You need dynamic selection (can't decide all at once)
  3. Optimal changes as you go (heap tracks current best)

Why not just sort everything? Because the optimal choice at step i depends on what you've selected in steps 1...i-1.

Template: Greedy + Priority Queue

python
import heapq

def greedy_with_heap(items, k):
    """
    Universal template for greedy + heap problems.
    Time: O(n log n) sort + O(n log k) heap ops
    Space: O(k) for heap
    """
    # Step 1: Sort by greedy criterion
    items.sort(key=lambda x: x.criterion)
    
    heap = []
    state = 0
    result = initial_value
    
    # Step 2: Process in sorted order
    for item in items:
        # Add to heap
        heapq.heappush(heap, item.value)
        state += item.contribution
        
        # Maintain size k (greedy eviction)
        if len(heap) > k:
            removed = heapq.heappop(heap)
            state -= removed
        
        # Update result when condition met
        if len(heap) == k:
            result = optimize(result, state, item)
    
    return result

Example 1: Meeting Rooms II

Problem: Given meeting intervals, find minimum rooms needed.

Greedy insight:

  • Sort by start time
  • Use heap to track ongoing meetings
  • When a meeting ends, reuse that room
python
import heapq

def minMeetingRooms(intervals):
    """
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return 0
    
    # Sort by start time (greedy ordering)
    intervals.sort(key=lambda x: x[0])
    
    # Min heap: track end times of ongoing meetings
    heap = []
    
    for start, end in intervals:
        # If earliest-ending meeting has ended, reuse room
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        
        # Add current meeting's end time
        heapq.heappush(heap, end)
    
    # Heap size = number of rooms needed
    return len(heap)

Why it works:

  • Heap always contains end times of currently ongoing meetings
  • heap[0] is the earliest ending meeting
  • If it's ended, we can reuse that room
  • Otherwise, we need a new room

Trace:

code
Intervals: [[0,30], [5,10], [15,20]]
After sort: [[0,30], [5,10], [15,20]]

i=0: [0,30]
  heap = [30]
  rooms = 1

i=1: [5,10]
  heap[0]=30 > 5, can't reuse
  heap = [10, 30]
  rooms = 2

i=2: [15,20]
  heap[0]=10 <= 15, reuse!
  pop 10
  heap = [20, 30]
  rooms = 2 (max)

Example 2: Minimum Cost to Hire K Workers

Problem: Hire exactly k workers minimizing total cost, with wage constraints.

Greedy insight:

  • Sort by wage/quality ratio
  • Use max heap to track k workers with highest quality
  • For each ratio, calculate cost if we hire workers up to this ratio
python
import heapq

def mincostToHireWorkers(quality, wage, k):
    """
    Time: O(n log n), Space: O(n)
    """
    # Create (ratio, quality) pairs
    workers = sorted((w/q, q) for w, q in zip(wage, quality))
    
    result = float('inf')
    quality_sum = 0
    max_heap = []  # Max heap (negate for min heap)
    
    for ratio, q in workers:
        # Add this worker's quality
        heapq.heappush(max_heap, -q)
        quality_sum += q
        
        # Keep only k workers with smallest quality
        if len(max_heap) > k:
            quality_sum += heapq.heappop(max_heap)  # Add negative = subtract
        
        # If we have k workers, calculate cost
        if len(max_heap) == k:
            result = min(result, quality_sum * ratio)
    
    return result

Why it works:

  • All workers must be paid at same ratio
  • For ratio r, cost = r × total_quality
  • We want minimum quality for each ratio
  • Heap maintains k workers with smallest quality

Example 3: Task Scheduler

Problem: Schedule tasks with cooldown period, minimize total time.

python
import heapq
from collections import Counter

def leastInterval(tasks, n):
    """
    Time: O(N log 26), Space: O(26)
    """
    # Count frequencies
    freq = Counter(tasks)
    
    # Max heap of frequencies
    max_heap = [-f for f in freq.values()]
    heapq.heapify(max_heap)
    
    time = 0
    
    while max_heap:
        temp = []
        
        # Process n+1 slots (one cycle)
        for _ in range(n + 1):
            if max_heap:
                freq = heapq.heappop(max_heap)
                if freq + 1 < 0:  # Still has tasks left
                    temp.append(freq + 1)
            time += 1
            
            # If no tasks left, break early
            if not max_heap and not temp:
                break
        
        # Put back remaining tasks
        for f in temp:
            heapq.heappush(max_heap, f)
    
    return time

When NOT to Use Heap

Don't use heap if:

  • ❌ You can sort once and iterate (no dynamic selection)
  • ❌ You need to access arbitrary elements (heap only gives min/max)
  • ❌ The optimal doesn't change as you process items

Use heap when:

  • ✅ Optimal element changes dynamically
  • ✅ Need to maintain "top k" or "next best"
  • ✅ Processing in one order, selecting in another

Common Mistakes

Mistake 1: Wrong Heap Type

❌ Wrong:

python
# Need max heap but using min heap
heapq.heappush(heap, value)  # Min heap

✅ Correct:

python
# Negate for max heap
heapq.heappush(heap, -value)
result = -heapq.heappop(heap)

Mistake 2: Forgetting to Maintain Size

❌ Wrong:

python
# Heap grows unbounded
heapq.heappush(heap, value)

✅ Correct:

python
heapq.heappush(heap, value)
if len(heap) > k:
    heapq.heappop(heap)

Mistake 3: Wrong Sort Criterion

❌ Wrong:

python
# Sorting by wrong attribute
items.sort(key=lambda x: x.value)

✅ Correct:

python
# Sort by the greedy criterion
items.sort(key=lambda x: x.ratio)

Complexity Analysis

Time Complexity:

  • Sort: O(n log n)
  • Heap operations: O(n log k) where k is heap size
  • Total: O(n log n)

Space Complexity:

  • Heap: O(k)
  • Total: O(k)

Conclusion

Greedy + priority queue is a powerful pattern for problems requiring dynamic optimal selection.

Remember:

  1. Sort by greedy criterion first
  2. Use heap to maintain optimal subset
  3. Update result as you process items

For more advanced techniques, see Advanced Greedy Techniques and the complete greedy guide.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials