Chapter notes

The heapsort algorithm was invented by Williams [316], who also described how to implement a priority queue with a heap. The BUILD-MAX-HEAP procedure was suggested by Floyd [90].

We use min-heaps to implement min-priority queues in Chapters 16, 23 and 24. We also give an implementation with improved time bounds for certain operations in Chapters 19 and 20.

Faster implementations of priority queues are possible for integer data. A data structure invented by van Emde Boas [301] supports the operations MINIMUM, MAXIMUM, INSERT, DELETE, SEARCH, EXTRACT-MIN, EXTRACT-MAX, PREDECESSOR, and SUCCESSOR in worst-case time O(lg lg C), subject to the restriction that the universe of keys is the set {1, 2, . . . , C}. If the data are b-bit integers, and the computer memory consists of addressable b-bit words, Fredman and Willard [99] showed how to implement MINIMUM in O(1) time and INSERT and EXTRACT-MIN in time. Thorup [299] has improved the bound to O((lg lg n)²) time. This bound uses an amount of space unbounded in n, but it can be implemented in linear space by using randomized hashing.

An important special case of priority queues occurs when the sequence of EXTRACT-MIN operations is monotone, that is, the values returned by successive EXTRACT-MIN operations are monotonically increasing over time. This case arises in several important applications, such as Dijkstra's single-source shortest-paths algorithm, which is discussed in Chapter 24, and in discrete-event simulation. For Dijkstra's algorithm it is particularly important that the DECREASE-KEY operation be implemented efficiently. For the monotone case, if the data are integers in the range 1, 2, . . . , C, Ahuja, Melhorn, Orlin, and Tarjan [8] describe how to implement EXTRACT-MIN and INSERT in O(lg C) amortized time (see Chapter 17 for more on amortized analysis) and DECREASE-KEY in O(1) time, using a data structure called a radix heap. The O(lg C) bound can be improved to using Fibonacci heaps (see Chapter 20) in conjunction with radix heaps. The bound was further improved to O(lg^1/3+∈ C) expected time by Cherkassky, Goldberg, and Silverstein [58], who combine the multilevel bucketing structure of Denardo and Fox [72] with the heap of Thorup mentioned above. Raman [256] further improved these results to obtain a bound of O(min(lg^1/4+∈ C, lg^1/3+∈ n)), for any fixed ∈ > 0. More detailed discussions of these results can be found in papers by Raman [256] and Thorup [299].