Java Reference
In-Depth Information
Chapter
26
A Heap
Implementation
Contents
Reprise: The ADT Heap
Using an Array to Represent a Heap
Adding an Entry
Removing the Root
Creating a Heap
Heap Sort
Prerequisites
Chapter
2
Bag Implementations That Use Arrays
Chapter
13
List Implementations That Use Arrays
Chapter
23
Trees
Objectives
After studying this chapter, you should be able to
•
Use an array to represent a heap
•
Add an entry to an array-based heap
•
Remove the root of an array-based heap
•
Create a heap from given entries
•
Sort an array by using a heap sort
R
ecall from Chapter 23 that a heap is a complete binary tree whose nodes are
ordered in a certain manner. When a binary tree is complete, you can use an array to
represent it in an efficient and elegant way. The most common implementation of a
heap uses an array, and that is the one we will describe in this chapter.
As you saw in Chapter 23, you can use a heap as an efficient implementation of
the ADT priority queue. Later, this chapter will show you how to sort an array by
using a heap.
