Lab: Heaps and Heap Sort

Summary: In this laboratory, you will explore the wonder of heaps.

Preparation

Fork and clone the repository at https://github.com/Grinnell-CSC207/heaps.

Import the repository into Eclipse.

Scan through the code so that you understand what methods are available and what approaches are used. Make notes on areas that are likely to be problematic.

Exercises

Exercise 1: Experiments

The file HeapExpt.java contains a few simple experiments with heaps. Pick one or two of those experiments, run the experiments, and check that the heaps created seem to be correct.

Exercise 2: Designing Heap Sort

As you may recall, the in-place heap sort algorithm has two phases. First, it turns the array into a heap. Then, it repeatedly swaps the largest remaining element to the appropriate place in the array.

Sketch invariants for each phase of heap sort.

Exercise 3: Heap Sort

The file HeapSorter.java contains a stub implementation of heap sort. Finish that implementation. You can check whether it works using HeapSorterTest.java.

Exercise 4: Swap Up, Revisited

Although we initially described the “swap up” algorithm recursively, Heap.java has an iterative implementation. Rewrite swapUp to use recursion.

Exercise 5: Swap Down, Revisited

We've both described and implemented the “swap down” algorithm recursively. However, as you know, many people prefer iteration to recursion. Rewrite swapDown to use iteration. You may not use break to escape from your loop. However, you may use a sentinel.

For Those With Extra Time

If you find that you have extra time, try any of the following problems.

Extra 1: A Heap Predicate

Write a predicate that checks if an array is in heap order. Your predicate should have a signature something like.

public static <T> boolean isHeap(T[] values, Comparator<T> order) 
{
   ....
} // isHeap

Extra 2: A Simple Iterator

Add an iterator to the Heap class. You may iterate the values in any order you find easy. (You are likely to find it easiest to iterate the values from left to right in the array.)

You need only implement the next and hasNext methods. (You will have the opportunity to implement the remove method in the next exercise.)

Extra 3: Removing Elements

Implement the remove method for the iterator from the previous problem.

Extra 4: Iterating Elements, Revisited

Implement an iterator that returns the values in order from largest to smallest. (Note: I know of no easy way to approach this problem.)