Previous Topic

What is a Priority Queue?

A priority queue is an abstract data type (ADT) that manages a collection of elements where each element has a priority (often a key). The data structure always returns the element with the best priority next. In a min-priority queue, the smallest key comes out first; in a max-priority queue, the largest does.

Unlike a regular queue (FIFO), the removal order is determined by priority, not insertion time. Priority queues are typically implemented with heaps to achieve good performance guarantees.

Core Operations

• insert(x, key): Add an element with a given priority.
• peek() or top(): Inspect the current best-priority element without removing it.
• extract() (extract-min or extract-max): Remove and return the best-priority element.
• decrease_key(x, new_key) / increase_key: Improve an element’s priority. Common in graph algorithms.
• merge (meld): Combine two priority queues into one (supported efficiently by some variants).

Additional considerations include how to compare priorities (custom comparator), how to handle ties (stable vs. unstable), and whether you need to locate and update arbitrary elements (an indexed priority queue).

Common Implementations and Trade-offs

Binary Heap (array-backed)

• Time complexity: insert O(log n), extract O(log n), peek O(1), decrease_key O(log n).
• Space: O(n) contiguous array; great cache locality.
• Representation: For 0-based indexing, parent(i) = floor((i-1)/2), left(i) = 2i+1, right(i) = 2i+2.
• Widely used default; excellent practical performance with small constants.

d-ary Heap

• Generalizes binary heap to d children per node.
• insert and decrease_key speed up as d increases; extract can get slower due to more children to scan.
• Good for workloads with frequent decrease_key (e.g., Dijkstra) and large branching factors.

Binomial Heap

• Supports efficient merge in O(log n).
• insert O(1) amortized, extract O(log n), decrease_key O(log n).
• Useful when melding queues is frequent.

Fibonacci Heap

• insert and decrease_key in O(1) amortized; extract O(log n) amortized.
• Strong theoretical guarantees for algorithms with many decrease_key operations.
• Large constant factors; less common in production compared to binary or pairing heaps.

Pairing Heap

• Simple meldable heap with excellent practical performance.
• Amortized bounds are favorable in practice; often competitive with binary heaps.

Balanced BST (e.g., red-black tree)

• insert, peek, extract, decrease_key all O(log n).
• Supports ordered iteration and duplicate handling naturally.
• Higher constant factors vs. binary heaps for pure PQ workloads.

Sorted/Unsorted Arrays or Lists

• Unsorted: insert O(1), extract O(n).
• Sorted: insert O(n), extract O(1).
• Sometimes best when one operation vastly dominates the other or for very small n.

Minimal Heap-based API Sketch

// Min-heap priority queue (0-based array A)
insert(x):
  A.append(x)
  sift_up(A.size-1)

peek():
  return A[0]

extract_min():
  swap A[0], A[last]
  min = A.pop()
  if A not empty: sift_down(0)
  return min

sift_up(i):
  while i > 0 and A[i] < A[parent(i)]:
    swap A[i], A[parent(i)]
    i = parent(i)

sift_down(i):
  while has_child(i):
    j = index of smaller child of i
    if A[i] <= A[j]: break
    swap A[i], A[j]
    i = j

Where Priority Queues Shine

• Graph algorithms: Dijkstra’s shortest path, Prim’s MST, A* search (with heuristics).
• Scheduling: CPU scheduling, job/task schedulers, bandwidth management.
• Discrete-event simulation: Process next event by earliest timestamp.
• Data processing: k-way merge, streaming top-k, median/quantile maintenance variants.
• Coding and compression: Huffman coding tree construction.

Variants and Specialized Structures

• Indexed priority queue: Track positions for efficient key updates/removals by handle.
• Double-ended priority queue: Supports both min and max (e.g., min-max heap).
• Bucket/radix queues: For small-integer priority ranges; can achieve near O(1) operations (e.g., Dial’s algorithm).
• Monotone priority queues: Priorities only decrease (or increase) over time; admit simpler/faster designs.
• Calendar queues: Optimized for event simulation with time-like keys.

Design Choices and Pitfalls

• Comparator: Define total order; be careful with floating-point NaNs and custom tie-breakers.
• Stability: Heaps are not stable by default; encode tiebreaks if needed.
• Updates: If priorities change after insertion, you need decrease/increase-key or remove+reinsert; consider an indexed PQ.
• Many equal priorities: Bucketing may outperform heaps.
• Concurrency: Global heap locks can bottleneck; consider sharded heaps or lock-free structures.
• Memory: Heaps are compact; node-based trees have pointer overhead.

Performance Summary

• Heap-based: insert O(log n), extract O(log n), peek O(1), decrease_key O(log n).
• Meldable heaps (binomial, Fibonacci, pairing): efficient merge; Fibonacci gives O(1) amortized insert/decrease_key.
• Balanced BST: All core ops O(log n), with ordered traversal support.

When Not to Use One

• Strict FIFO/LIFO requirements (use queues/stacks).
• You need stable ordering without custom tiebreaking.
• Data size is tiny and constant; a simple array or small sorted list might be faster.

Next Topic