Data Structures the Fun Way

7 Priority Queues and Heaps

Priority queues are a class of data structures that retrieve items ordered by given scores for each item. Whereas both stacks and queues from Chapter 4 depended solely on the order in which data was inserted, priority queues use an additional piece of information to determine the retrieval order—the item’s priority. As we will see, this new information allows us to further adapt to the data and, among other useful applications, allows us to process urgent requests first.

For example, imagine a new coffee shop, Dynamic Selection Coffee, has opened in your neighborhood. Bursting with excitement, you venture into ...