Chapter 8. Heaps and Priority Queues

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

Get Data Structures and Algorithms in C++, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.