Data Structures and Algorithms in C++, Second Edition

Chapter 8. Heaps and Priority Queues

Contents

8.1 The Priority Queue Abstract Data Type	322
8.1.1 Keys, Priorities, and Total Order Relations	322
8.1.2 Comparators	324
8.1.3 The Priority Queue ADT	327
8.1.4 A C++ Priority Queue Interface	328
8.1.5 Sorting with a Priority Queue	329
8.1.6 The STL priority_queue Class	330
8.2 Implementing a Priority Queue with a List	331
8.2.1 A C++ Priority Queue Implementation using a List	333
8.2.2 Selection-Sort and Insertion-Sort	335
8.3 Heaps	337
8.3.1 The Heap Data Structure	337
8.3.2 Complete Binary Trees and Their Representation	340
8.3.3 Implementing a Priority Queue with a Heap	344
8.3.4 C++ Implementation	349
8.3.5 Heap-Sort	351
8.3.6 Bottom-Up Heap Construction*	353
8.4 Adaptable Priority Queues	357
8.4.1 A List-Based Implementation	358
8.4.2 Location-Aware Entries	360
8.5 Exercises	361

The Priority Queue Abstract Data Type

A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion but supports removal of elements in order of priority, that is, the element with first priority can be removed at any time. This ADT is fundamentally different from the position-based data structures such as stacks, queues, deques, lists, and even trees, we discussed in previous chapters. These other data structures store elements at specific positions, which are often positions in a linear arrangement of the elements determined by ...