Learning Algorithms

Chapter 4. Heaping It On

In this chapter, you will learn:

• The queue and priority queue data types.

• The binary heap data structure, invented in 1964, which can be stored in an array.

• That in a max binary heap, an entry with a larger numeric priority is considered to have higher priority than an entry with a smaller numeric priority. In a min binary heap, entries with smaller numeric priority have higher priority.

• How to enqueue a (value, priority) entry to a binary heap in O(log N), where N is the number of entries in the heap.

• How to find the value with highest priority in a binary heap in O(1).

• How to remove the value with highest priority from a binary heap in O(log N).

Instead of just storing a collection of values, what if you stored a collection of entries, where each entry has a value and an associated priority represented as a number? Given two entries, the one whose priority is higher is more important than the other. The challenge this time is to make it possible to insert new (value, priority) entries into a collection and be able to remove and return the value for the entry with highest priority from the collection.

This behavior defines a priority queue—a data type that efficiently supports enqueue(value, priority) and dequeue(), which removes the value with highest priority. The priority queue is different from the symbol table discussed in the previous chapter because you do not need to know the priority in advance when requesting to remove the value ...