Skip to main content

Priority-Queue Applications: Simulation, Dijkstra, Top-K, Median

What This Concept Is​

Priority queues fit loops that repeatedly choose an extreme from a changing set. Applications include next-event simulation, bounded top-K, merging sorted streams, running medians, and graph algorithms. Each application needs a second invariant connecting heap contents to the problem; heap order alone proves little about the application's correctness.

Why It Matters Here​

This is the bridge to graph algorithms. Before using a queue in a more complex proof, make explicit what is represented, what may be missing, and whether an entry can be stale. A min-heap does not by itself make a shortest-path algorithm correct or a scheduler fair.

Concrete Examples​

For K sorted streams, keep one current head per nonempty stream. The smallest head is the smallest remaining element globally: every unread item in a stream is at least that stream's head. Emit it and replace it from the same stream. Initialization inspects K streams and can heapify heads in O(K); N emissions cost O(N log(K+1)), with O(K) extra slots. Empty streams, K=0, and K=1 fit this bound. Collecting output in a list adds O(N) caller storage.

For largest-K streaming values, retain a min-heap of at most K records. Until full, insert. Then discard arrivals no greater than the minimum, or replace the minimum with a greater arrival. Inductively the heap contains a valid largest-K multiset from the processed prefix. Handle K=0 explicitly; sorting retained records for final presentation adds O(K log K).

Common Confusion / Misconceptions​

Two-heap median maintenance needs both size balance and partition order: every lower-half key is no greater than every upper-half key. Balancing sizes alone is insufficient. Define the even-count median convention before choosing an output. Dijkstra additionally needs nonnegative edge weights and a rule for ignoring stale tentative distances; it belongs to the next module. Scheduling by minimum timestamp does not guarantee fairness or causality on its own.

How To Use It​

For streamed merging, use (value,stream_index) so equal heads have a defined tie break without comparing iterators. The lab processes finite integer streams and leaves I/O buffering to the caller. For events, use a monotonically increasing sequence number for FIFO ties and a documented policy for events scheduled in the past. For a graph queue, distinguish discovered, pending, and finalized state.

Check Yourself​

  1. Why is a stream's head enough to represent all of its unread elements?
  2. Where does the K initialization term come from?
  3. What does a top-K heap know that its internal array order does not show?
  4. Which invariant besides heap sizes is needed for running medians?

Mini Drill or Application​

Merge [1,4], [], and [1,2,5] using a table of heap heads after each output. Prove multiplicity preservation. Instrument generators to reject eager input consumption. Extension: implement a top-K stream and compare each prefix against a full-sort oracle; test K=0 and K larger than the prefix. See P16 and Lab D.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for multiway merging, top-K streams, and application invariants. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.