Java Software Structures, 4th Edition Exercise Solutions, Ch. 12
Chapter 12 Exercise Solutions
EX 12.1 Draw the heap that results from adding the following integers (34 45 3 87 65 32 1 12 17).
1
12
3
EX 12.2 Starting with the resulting tree from Exercise 12.1, draw the tree that results from
performing a removeMin operation.
3
12
32
EX 12.3 Starting with an empty minheap, draw the heap after each of the following operations:
addElement(40);
addElement(25):
removeMin();
addElement(10);
removeMin();
Java Software Structures, 4th Edition Exercise Solutions, Ch. 12
25
10
1
5
EX 12.4 Repeat Exercise 12.3, this time with maxheap.
To use a maxheap, we will assume that the removeMin operations are removeMax.
After the first two addElement operations:
40
Java Software Structures, 4th Edition Exercise Solutions, Ch. 12
After removing the maximum and adding the elements 5 and 1:
10
45 1
5
EX 12.5 Draw the UML description for the PriorityQueue class described in this chapter.
ArrayBinary
Tree
BinaryTree
ADT
EX 12.6 Draw the UML description for the array implementation of heap described in this
chapter.
ArrayBinary
Tree
BinaryTree
ADT