In this chapter
- introducing the priority queue abstract data type
- the difference between queue and priority queue
- implementing a priority queue with arrays and linked lists
- introducing the heap, a data structure for the priority queue abstract data type
- why heaps are implemented as arrays rather than trees
- how to efficiently build a heap from an existing array
In chapter 9, we talked about queues, a container that holds your data and returns it in the same order in which it was inserted. This idea can be generalized by introducing the concept of priority, which leads us to priority queues and their most common implementation—heaps. In this chapter, we discuss both, together with some of their applications.
Extending queues with priority
In the previous chapter, we saw some examples of queues in real life, such as the line to get an ice cream. Not all queues, however, have such a linear development. In an emergency room, for example, the next person to see a doctor isn’t necessarily the person who has waited the longest, but rather the one who needs the most urgent care. And the order is dynamic, not set in stone.
In this section, we introduce the concept of priority and derive from that a variant of the plain queue called priority queue.