CMPS 144L: Programming Lab Activity on Max-Heaps

An instance of the MaxHeapOfInt class represents, as its name suggests, a max-heap containing integers. Five of its methods are stubbed: getMax(), siftUp(), siftUpRec(), siftDown(), and siftDownRec().

Before attempting to complete any of the methods just mentioned, you should scan the entire class in order to find methods that may be useful to you. In particular, notice the methods in the section labeled "private methods" that precede the heapify() method.

To complete getMax() should be a no-brainer.

It is recommended that you next try to complete either siftUp() or siftUpRec(). They are intended to have the same observable behavior, but the intent is for the former to include a loop and for the latter to be recursive (and thus include a call to itself). (If you complete siftUpRec(), modify the insert() method to call it rather than calling siftUp().)

To test the correctness of your methods, use the HeapTester application by choosing to start with an empty heap and then trying to do some insertions (by invoking the Insert value into heap option).

After getting either siftUp() or siftUpRec() to work, focus your attention upon siftDown() (or siftDownRec(), which is intended to be the recursive version), which is similar in concept to siftUp() but somewhat trickier to implement. A good way to test the correctness of siftDown() is to choose either the Load some values into a new heap option or the Delete max value from heap option. (If you implement siftDownRec(), modify the deleteMax() method to call it rather than calling siftDown().)

Sample Dialog with HeapTester:

Notice that the "Display heap" option causes the heap to be displayed, but rotated by 90 degrees. Each node's ID, as well as the datum that it holds, are displayed. 

$ java HeapTester
Welcome to the Heap Tester program.

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 3
Enter a number to insert: 5

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 3
Enter a number to insert: 9

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 3
Enter a number to insert: 0

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 6
   2:0
0:9
   1:5

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 3
Enter a number to insert: 12

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 3
Enter a number to insert: -5

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 6
   2:0
0:12
      4:-5
   1:9
      3:5

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 4
12

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 2
Enter (one or more) values to load into a new heap: 12 0 17 19 -3 45 21 18 6 9

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 6
      6:12
   2:21
      5:17
0:45
      4:9
         9:-3
   1:19
         8:6
      3:18
         7:0

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 5

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 6
      6:12
   2:17
      5:-3
0:21
      4:9
   1:19
         8:6
      3:18
         7:0

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 5

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 6
      6:12
   2:17
      5:-3
0:19
      4:9
   1:18
      3:6
         7:0

(1) Create new empty heap         (2) Load some values into a new heap
(3) Insert value into heap        (4) Show max value in heap
(5) Delete max value from heap    (6) Display heap
(7) Quit
> 7
Goodbye from the Heap Tester program.