The Algorithm Design Manual Second Edition

Stop and Think: Basic Priority Queue Implementations

Problem: What is the worst-case time complexity of the three basic priority queue

operations (insert, find-minimum, and delete-minimum) when the basic data struc-

ture is

• An unsorted array.

• A sorted array.

• A balanced binary search tree.

Solution: There is surprising subtlety in implementing these three operations, even

when using a data structure as simple as an unsorted array. The unsorted array

---

3 . 6

W A R S T O R Y : S T R I P P I N G T R I A N G U L A T I O N S

85

For sorted arrays, we can implement insert and delete in linear time, and mini-

mum in constant time. However, all priority queue deletions involve only the min-

imum element. By storing the sorted array in reverse order (largest value on top),

the minimum element will be the last one in the array. Deleting the tail element

requires no movement of any items, just decrementing the number of remaining

items n, and so delete-minimum can be implemented in constant time.

All this is fine, yet the following table claims we can implement find-minimum

in constant time for each data structure:

Unsorted

Sorted

Balanced

array

array

tree

Insert(Q, x)

O(1)

O(n)

O(log n)

Find-Minimum(Q)

O(1)

O(1)

O(1)

Delete-Minimum(Q)

O(n)

O(1)

O(log n)

The trick is using an extra variable to store a pointer/index to the minimum

entry in each of these structures, so we can simply return this value whenever we

are asked to find-minimum. Updating this pointer on each insertion is easy—we

update it if and only if the newly inserted value is less than the current minimum.

But what happens on a delete-minimum? We can delete the minimum entry have,

then do an honest find-minimum to restore our canned value. The honest find-

minimum takes linear time on an unsorted array and logarithmic time on a tree,

and hence can be folded into the cost of each deletion.

Priority queues are very useful data structures. Indeed, they will be the hero of

two of our war stories, including the next one. A particularly nice priority queue

implementation (the heap) will be discussed in the context of sorting in Section

4.3

(page

108

). Further, a complete set of priority queue implementations is presented

in Section

12.2

(page

373

) of the catalog.