CS151 Lab11:  It's the Last Lab, so Heap It On!

 

Home Search E-mail Java Resources Discussion
Demo

Final Project Milestone

Due Fri. 9:00 AM, May 4, 2000 (i.e. by class)

Each group must hand-in working code that demonstrates:

  1. Inter-computer communication
  2. Proper operation of agreed upon protocols.
    1. All inter-computer commands must be implemented to the point that the receiver clearly recognizes the command and is performing a unique operation for it (i.e. just printing out the received command is not enough.   A command-specific method must be dispatched.)
    2. The protocol structure should be within  minor tweaks of being finalized.

As the end of the semester is approaching, and because this is a milestone, not the final product, late turn-ins are very strongly discouraged!  

If you are having trouble getting the code working, you must see your faculty mentor before the due date!

Heaps  

Due Sunday 11:59 PM, May 6, 2000

In this lab, you will explore the wonderful world of heaps.

First you will write an extensive test program for the heap and its operations.  Then you will write the heap sort algorithm and incorporate it into the rest of your sorters.    Use the demo programs in the next section and in the sorter lab as a guide for what you need to do.

The Algorithms

There are a couple of basic algorithms that you need to establish before attempting to heapify, insert, remove or sort.

See the lecture notes for detailed discussions of heaps and their associated algorithms.   Carefully study the on-line demo to the left.   

Write and test the folowing algorithms in the order discussed below:

Display Algorithm

  1. Create a test program in a HeapTest package.
  2. You will need your Sorter package.
  3. Download HeapTest.HeapDisplayAdapter.java , which is a modified BRSDisplayAdapter.   
    1. HeapDisplayAdapter and BRSDisplayAdapter work in essentially the same way, i.e. it will display a breadth-first representation of the array as a tree on a JPanel.  
    2. HeapDisplayAdapter.displayTree(Object[] tree, int length)  takes an array of Objects and the length of the tree in the array (starting at 0), in case you don't want to display the whole array.
  4. Add a timer that calls the display adapter's showTree() method and also writes the content of the array out to text area.    A delay of 100ms is about right.   Be sure that it is shorter than the delay of the GraphicOrder you might want to use to change the color of the compared objects.   Don't forget to start the timer up!
  5. Add a button to create a random sized array of Objects filled with random ColoredIntegerAdapters.     At this point it doesn't matter if you use SorterColors or regular Colors, as there will be no split/join recoloring.
  6. Test that your program will generate the random array and display it properly.   Note:  Be sure to initialize your array to at least one element so the animation subsystem will have something to plot right away.

All of the algorithms below should be started up on their own threads so the animation will work.

Sift-Down Algorithm

First carefully study the lecture notes on sifting down.  The discussion below presumes you understand the algorithm already.

  1. Make a class in the Sorter package called "Heapifier".  We will put the main heap utility algorithms in this class for testing now and later use.    Make Heapifier a singleton class.
  2. The intention here is eventually use these algorithms in a generic Sorting algorithm.   This means that we cannot guarantee that the heap starts at the beginning of the array.  
    1. All we can say is that the heap starts at an index "lo" and goes inclusively to an index "hi".
    2. Modify the mathematical formulas to include the "lo" offset:  
      1. The easiest way is to subtract "lo" off any actual index before using it a math calculation
      2. Before using any mathematically calculated index, add "lo" to it.
  3. The siftDown() method of Heapifier should take the array, lo, hi, and the current node (the parent) plus an AOrder strategy.
  4. The first thing to do is to find the smallest child.   Be careful here, as there some pitfalls:
    1. Does the node have a child?   How can you determine if a node is a leaf?
    2. If it has one child, does it have the second one as well?
    3. Does the parent care which child is smaller?  Or just that it be handed a child to compare and perhaps swap with?
  5. Having found the smallest child, if there is a child at all, simply compare against the parent and swap if the child is smaller.
  6. If you swap, recur into the child.  That is, the child is now the parent.
  7. Thoroughly test your algorithm before proceeding.

 

Heapify Algorithm

A heapify algorithm makes an arbitrary array into a heap by successively applying a sift down algorithm.

  1. The heapify() method of Heapify should take the array, lo and hi.
  2. Calculate the the last element that is not a leaf.   Hint:  Whose parent is that element?
  3. Sift-down that node.
  4. Work your way back to the front of the heap (lo).

Test your heapify algorithm carefully.

Sift-up Algorithm

The sift-up algorithm is simply a recursive comparison of a node with its parent, swapping if necessary and the continuing on upwards through the heap.

  1. The siftUp() method of Heapify should take the array, lo and the current node plus an AOrder strategy.
  2. Calculate the parent of the current node.  
  3. If a parent exists, then swap the elements if the child is smaller than the parent.
  4. Recur into the parent.  That is, make the parent the current node.

Test your algorithm thoroughly.

Removing An Element From The Heap And Putting It At The End Of The Array

  1. Create a treeLength variable in your test code (not in Heapifier).   This variable represents the logical size of the heap's array, which may not match it's actual physical size.
  2. Whenever you create a new array, reinitialize treeLength to the length of the new array.
  3. Change the first element's color to something that is neither the normal or compare color.
  4. Swap the first element of the array with the last element, whose index is treeLength-1. 
  5. Decrement treeLength to insure that the old first element is now outside the heap.
  6. Sift-down the new top element.

What does repeatedly pressing the Remove button do? 

Inserting An Element Into The Heap.

  1. Create a button that will insert a value into the array at the end of its logical size (i.e. at treeLength):
    1. Create a new array that is one larger than the actual physical size of the current array.
    2. Copy the first treeLength elements to the new array.
    3. Copy in the new element to the new array.
    4. Copy the rest of the original array to the new array.   Remember that the index in the new array won't match the index in the old array any more!
    5. Set the original array's variable to reference the new array.
    6. Increment the size of treeLength.
  2. Sift up the newly inserted element.

Test your code carefully, especially for the cases when treeLength does not equal array.length.   You can achieve this by removing several elements and then inserting one.

HeapSort

It should be pretty obvious by now how to make a HeapSorter class.   Install a heap sort capability into your sorter test program from the previous lab.

One thing to be sure to do is that as soon as the heap sorter is selected, the array needs to be heapified.

Your HeapSort will probably sort backwards from the rest of your sorters.   Earn 5 brownie points for making it sort the same way!