14.12 Priority Queue Greedy

Many greedy algorithms appear different on the surface.

algorithmsgreedy

14.12 Priority Queue Greedy

Many greedy algorithms appear different on the surface. One schedules jobs, another allocates resources, another computes shortest paths, and another determines refueling stops. Yet a surprising number share the same implementation pattern:

Repeatedly select the best available candidate.

The challenge is maintaining the set of candidates efficiently.

A priority queue solves this problem. Instead of repeatedly scanning all possibilities, the algorithm maintains candidates in a structure that can immediately return the most desirable one.

This combination of greedy selection and priority queues is one of the most important design patterns in algorithm engineering.

Problem

You have a collection of candidate actions.

At each step:

  1. New candidates may become available.
  2. Existing candidates may remain available.
  3. The algorithm must choose the best available candidate.

Examples include:

  • Selecting the highest-profit job.
  • Choosing the largest fuel station.
  • Extracting the closest vertex.
  • Picking the next event in a simulation.
  • Allocating the most valuable resource.

The naive solution repeatedly scans all candidates.

The priority queue solution maintains them in sorted order dynamically.

Motivation

Suppose we process jobs arriving over time.

Time Job Profit
1 A 100
2 B 50
3 C 200
4 D 75

At time 4, the available jobs are:

A B C D

The best choice is:

C

A linear scan requires examining every job.

A max-heap returns the answer immediately.

The Priority Queue Pattern

Most priority-queue greedy algorithms follow this structure:

Initialize priority queue

For each event:
    Add newly available candidates

    Remove expired candidates

    Choose best available candidate

The exact definition of "best" depends on the problem.

Example: Meeting Room Allocation

Suppose meetings arrive sorted by start time.

Meeting Start End
A 1 4
B 2 5
C 7 9

Goal:

Determine the minimum number of rooms required.

Greedy Observation

When a meeting begins:

  • If a room has become free, reuse it.
  • Otherwise allocate a new room.

The most useful room to track is:

The room that becomes available earliest.

This suggests a min-heap ordered by ending time.

Walkthrough

Meeting A:

Heap = [4]
Rooms = 1

Meeting B:

2 < 4

No room available.

Allocate another.

Heap = [4,5]
Rooms = 2

Meeting C:

7 >= 4

Room becomes free.

Reuse it.

Heap = [5,9]
Rooms = 2

Answer:

2

The heap efficiently tracks the next room that becomes available.

Example: Minimum Refueling Stops Revisited

From the previous recipe:

Target = 100
Fuel = 10

Stations:

(10,60)
(20,30)
(30,30)
(60,40)

The algorithm stores fuel amounts in a max-heap.

When fuel runs out:

Extract largest fuel amount

The heap guarantees the optimal greedy choice is available in:

O(log n)

time.

Without the heap, every refueling decision requires rescanning all previous stations.

Example: Course Scheduling

Consider courses:

Course Duration Deadline
A 100 200
B 200 1300
C 1000 1250
D 2000 3200

The prefix-constraint algorithm:

  1. Sorts by deadline.
  2. Adds durations to a max-heap.
  3. Removes the largest duration whenever feasibility is violated.

The heap maintains:

The worst job currently accepted.

This allows repairs in logarithmic time.

Anatomy of a Heap-Based Greedy Algorithm

Most implementations contain three operations.

Insert Candidate

push(candidate)

Candidate becomes available.

Remove Best Candidate

pop()

Candidate selected by the greedy rule.

Inspect Best Candidate

top()

Used when the algorithm needs information without removing the candidate.

Max-Heaps vs Min-Heaps

The choice depends on the optimization objective.

Max-Heap

Returns largest value.

Useful for:

  • Highest profit
  • Largest fuel amount
  • Longest duration
  • Largest priority

Min-Heap

Returns smallest value.

Useful for:

  • Earliest finish time
  • Shortest distance
  • Smallest deadline
  • Lowest cost

The heap should expose the quantity that drives the greedy decision.

Go Heap Interface

Go provides heap support through the standard library.

Min-heap example:

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

Usage:

heap.Init(&h)
heap.Push(&h, 10)
heap.Push(&h, 5)

smallest := heap.Pop(&h).(int)

Result:

5

Complexity Benefits

Without a heap:

Repeated scan

Complexity:

$$ O(n^2) $$

With a heap:

Insert = O(log n)
Remove = O(log n)

Total:

$$ O(n \log n) $$

This improvement often makes the difference between an impractical solution and a scalable one.

Recognizing the Pattern

Several signals suggest a priority queue.

Repeated Best Choice

The algorithm repeatedly selects:

largest
smallest
highest
lowest
best

candidate.

Dynamic Candidate Set

Candidates appear and disappear over time.

Local Optimal Selection

The greedy choice depends only on currently available options.

Expensive Linear Scans

The implementation repeatedly searches for a minimum or maximum.

A heap often eliminates that bottleneck.

Common Greedy Problems Using Heaps

Problem Heap Type
Dijkstra Min-heap
Prim Min-heap
Minimum refueling stops Max-heap
Course scheduling Max-heap
Meeting rooms Min-heap
Event simulation Min-heap
Top-K elements Min-heap
Streaming median Min + Max heap

Although the underlying problems differ dramatically, the implementation pattern remains remarkably consistent.

Common Mistakes

Choosing the Wrong Heap Direction

Using a min-heap when the greedy rule requires the largest element.

Forgetting Expired Candidates

Candidates that are no longer feasible must often be removed.

Rebuilding the Heap

Some implementations reconstruct the heap repeatedly.

This destroys the performance benefit.

Confusing Sorting with a Heap

Sorting gives a static ordering.

A heap supports dynamic insertion and removal.

Many greedy algorithms need both.

Sorting Plus Heap

A common pattern combines the previous recipe with this one.

Example:

Sort jobs by deadline.
Maintain active jobs in heap.
Perform greedy updates.

Many advanced scheduling algorithms use exactly this architecture.

The sort establishes processing order.

The heap manages dynamic choices.

Design Checklist

When building a greedy algorithm, ask:

  1. What is the greedy choice?
  2. Which quantity determines that choice?
  3. Do candidates appear dynamically?
  4. Is repeated scanning expensive?
  5. Would a heap expose the desired element efficiently?

If the answers align, a priority queue is usually the correct data structure.

Takeaway

Priority queues provide an efficient implementation framework for a large class of greedy algorithms. Whenever a problem repeatedly selects the best available candidate from a dynamically changing set, a heap often reduces the complexity from quadratic to logarithmic per operation. The key design step is identifying the quantity that defines "best" and exposing that quantity through either a min-heap or max-heap. Once that choice is made, many sophisticated greedy algorithms reduce to a simple loop of inserting candidates, removing the best candidate, and maintaining a small set of invariants.