Skip to main content

Heapsort and the Heap-Based Priority Queue API

What This Concept Is​

Heapsort builds a max-heap, swaps its root with the last active position, shrinks the heap prefix, and repairs the root. The invariant is that the prefix is a max-heap, the suffix is sorted, and every prefix key is no larger than any suffix key. At termination the whole array is sorted. Iterative sift-down uses O(1) auxiliary slots and worst-case sorting time is O(n log n).

A priority queue is the interface for adding records and retrieving an extreme priority; a binary heap is one implementation. Sorting drains it, while a long-lived queue interleaves operations.

Why It Matters Here​

An API needs more than a complexity label: missing entries, duplicate priorities, identity, stale handles, priority changes, and tie order all need definitions. Supporting decrease_key is different from appending an immutable value.

Concrete Examples​

Suppose jobs A and B both have priority 2. A heap comparing only priority may return either first. Store (priority,sequence_number,job) when FIFO ties matter; the unique sequence number also prevents comparing arbitrary job payloads.

To support decrease-key in O(log n) sift work, keep a map from job identity to its current heap index and update that map on every swap. Searching the heap for the job first can cost O(n). An alternative inserts a new version and skips stale entries when popped; physical heap size can then exceed the number of live jobs. The memory and operation bounds must use the physical entries until cleanup.

Common Confusion / Misconceptions​

Heapsort is not stable: moving a root to the suffix can reverse equal-key records. An API that mutates its array is not necessarily O(1) auxiliary space; check the implementation. Heap meld is not intrinsically fast for binary heaps: concatenate and heapify in O(n+m), or choose a different structure with a suitable meld bound. Library sort implementation names and fallback choices are version-specific.

How To Use It​

Choose whether the queue exposes handles, identity-based changes, cancellation, or only immutable pushes. Define whether stale entries count against capacity. For a minimal queue, implement push/peek/pop first, then add features with their own invariants. In this module decrease-key is a design exercise; Lab D's heap has immutable values and no handle map.

Check Yourself​

  1. What makes the sorted suffix safe after each heapsort extraction?
  2. Why does decrease-key need a location mechanism?
  3. What changes in the bound when stale entries accumulate?
  4. How can ties avoid comparing payload objects?

Mini Drill or Application​

Implement iterative heapsort as an extension and give a tagged equal-key counterexample to stability. Design a cancellable scheduler with either indexed deletion or versioned lazy entries. State maximum retained state and a cleanup policy; test cancellation followed by reinsertion of the same job identity. See P14 and the capstone thread.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for heapsort, priority-queue contracts, and indexed updates. 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.