O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required