Object-Oriented Data Structures Using Java, 4th Edition

CHAPTER 9: The Priority Queue ADT

© Ake13bk/Shutterstock

Knowledge Goals

You should be able to

• describe a priority queue at the abstract level

• discuss uses for a priority queue

• discuss alternative implementation approaches for a priority queue and their efficiencies

• define full and complete binary trees

• describe the shape and order properties of a heap

• define the heap operations reheap up and reheap down

• describe how a binary tree can be represented as an array, with implicit positional links between elements

Skill Goals

You should be able to

• given a binary tree, identify whether it is full, complete, both, or neither

• given an array-based representation of a binary tree and an index indicating a node of the tree, determine the ...