Chapter 15
Heaps
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-2
Chapter Objectives
•
Define a heap abstract data structure
•
Demonstrate how a heap can be used
to solve problems
•
Examine various heap impmentations
•
Compare heap implementations
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-3
Heaps
•
A heap is a binary tree with two added
properties:
–
It is a complete tree
–
For each node, the node is less than or
equal to both the left child and the right
child
•
This definition described a minheap
Copyright © 2005 Pearson

Addison-Wesley. All rights
reserved. 15-4
Heaps
•
In addition to the operations inherited
from a binary tree, a heap has the
following additional operations:
–
addElement
–
removeMin
–
findMin
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-5
FIGURE 15.1
The operations on a heap
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-6
Listing 15.1
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-7
FIGURE 15.2 UML description
of the HeapADT
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-8

The addElement Operation
•
The addElement method adds a given
element to the appropriate location in
the heap
•
A binary tree is considered complete if
all of the leaves are level h or h-1
where h = log
2
n and n is the number of
elements in the tree
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-9
The addElement Operation
•
Since a heap is a complete tree, there
is only one correct location for the
insertion of a new node
–
Either the next open position from the left
at level h
–
Or the first position in level h+1 if level h is
full
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-10
The addElement Operation

•
Once we have located the new node in the
proper position, then we must account for
the ordering property
•
We simply compare the new node to its
parent value and swap the values if
necessary
•
We continue this process up the tree until
either the new value is greater than its
parent or the new value becomes the root of
the heap
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-11
FIGURE 15.3 Two minheaps
containing the same data
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-12
FIGURE 15.4
Insertion points for a heap
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-13
FIGURE 15.5
Insertion and reordering in a heap
Copyright © 2005 Pearson
Addison-Wesley. All rights

reserved. 15-14
The removeMin Operation
•
The removeMin method removes the
minimum element from the heap
•
The minimum element is always stored
at the root
•
Thus we have to return the root
element and replace it with another
element
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-15
The removeMin Operation
•
The replacement element is always the
last leaf
•
The last leaf is always the last element
at level h
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-16
FIGURE 15.6
Examples of the last leaf in a heap
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-17

The removeMin Operation
•
Once the element stored in the last leaf has
been moved to the root, the heap will have to
reordered
•
This is accomplished by comparing the new
root element to the smaller of its children and
the swapping them if necessary
•
This process is repeated down the tree until
the element is either in a leaf or is less than
both of its children
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-18
FIGURE 15.7
Removal and reordering in a heap
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-19
Using Heaps: Heap Sort
•
Given the ordering property of a heap,
it is natural to think of using a heap to
sort a list of objects
•
One approach would be to simply add
all of the objects to a heap and then
remove them one at a time in

ascending order
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-20
Using Heaps: Heap Sort
•
Insertion into a heap is O(log n) for any given
node and thus would O(n log n) for n nodes
to build the heap
•
However, it is also possible to build a heap in
place using an array
•
Since we know the relative position of each
parent and its children in the array, we
simply start with the first non-leaf node in the
array, compare it to its children and swap if
necessary
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-21
Using Heaps: Heap Sort
•
However, it is also possible to build a heap in
place using an array
•
Since we know the relative position of each
parent and its children in the array, we
simply start with the first non-leaf node in the
array, compare it to its children and swap if

necessary
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-22
Using Heaps: Heap Sort
•
We then work backward in the array until we
reach the root
•
Since at most, this will require us to make
two comparisons for each non-leaf node, this
approach is O(n) to build the heap
•
We will revisit the analysis of HeapSort at
the end of the chapter
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-23
Using Heaps: Priority Queue
•
A priority queue is a collection that follows
two ordering rules:
–
Items which have higher priority go first
–
Items with the same priority use a first in, first out
method to determine their ordering
•
A priority queue could be implemented using
a list of queues where each queue

represents items of a given priority
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-24
Using Heaps: Priority Queue
•
Another solution is to use a minheap
•
Sorting the heap by priority accomplishes the
first ordering
•
However, the first in, first out ordering for
items with the same priority has to be
manipulated
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 15-25
Using Heaps: Priority Queue
•
The solution is to create a PriorityQueueNode object
that stores the element to be placed on the queue,
the priority of the element and the arrival order of
the element
•
Then we simply define a compareTo method for the
PriorityQueueNode class that first compares priority
then arrival time
•
The PriorityQueue class then extends the Heap
class and stores PriorityQueueNodes