Grokking Data Structures

10 Priority queues and heaps: Handling data according to its priority

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 ...