C++ Plus Data Structures, 6th Edition

CHAPTER 9: Heaps, Priority Queues, and Heap Sort

© Repina Valeriya/Shutterstock

After studying this chapter, you should be able to

• Describe a priority queue at the logical level and implement a priority queue as a list

• Show how a binary tree can be represented in an array, with implicit positional links between the elements

• Define the terms full binary tree and complete binary tree

• Describe the shape and order properties of a heap, and implement a heap using a tree represented by implicit links in an array

• Implement a priority queue as a heap

• Compare the implementations of a priority queue using a heap, a linked list, and a binary search tree

• Sort a set of values using a heap

Up to now, we have examined several basic data types in ...