Espresso: A Concentrated Introduction to Java

Laboratory: Heaps and Heap Sort

Summary: In this laboratory, you will have an opportunity to enhance your understanding of heaps by working with an implementation of heaps.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Comparing Elements
  • Exercise 2: Finding Positions
  • Detour: An Alternate Implementation
  • Exercise 3: Code Reading
  • Exercise 4: A Simple Heap
  • Exercise 5: Additional Testing
  • Exercise 6: Swapping Down
  • Exercise 7: Full Heaps

Required Code Files:

• IntHeap.java
• IHTester.java

Exercises

Exercise 0: Preparation

a. Create a package named username.heaps.

b. Put IntHeap.java and IHTester.java in that package.

Exercise 1: Comparing Elements

A key issue in the implementation of heaps is how we are to compare the elements to determine whether one value is smaller than another (and, therefore, whether two values might potentially be swapped).

Explain how we might do such a comparison.

Exercise 2: Finding Positions

Make sure to do this exercise with at least one colleague!

As you may recall, the algorithm for get in heaps is as follows:

• Determine and remember the value at the root.
• Place the value in the rightmost leaf at the lowest level at the root.
• Remove the rightmost leaf at the lowest level.
• Swap down, starting at the root.

The swap down step is fairly straightforward: You determine the value at the root of each subtree and, if the current value is smaller, you swap with the smaller of the two values and recurse.

Unfortunately, it is less straightforward to find the rightmost leaf at the lowest level.

Sketch an algorithm that permits us to find the rightmost leaf at the lowest level.

Detour: An Alternate Implementation

Because of the problems with finding and deleting the rightmost leaf, heaps are often implemented by storing the tree in an array. Please read Storing Heaps in Arrays for more details.

Exercise 3: Code Reading

a. This alternate implementation of heaps is partially coded as the Java class IntHeap.java.

Read through that code and determine what needs to be done to finish the implementation.

b. A tester for this class can be found in IHTester.java.

Read through that code and explain what it does.

Exercise 4: A Simple Heap

a. Sketch the series of heaps you expect to see when adding the values 4 2 1 5 2 0 to an empty heap.

b. Run IHTester and see if it creates the same heaps.

Exercise 5: Additional Testing

Run some additional tests to verify that the put method behaves as you expect for small heaps.

Exercise 6: Swapping Down

As you may have observed, the get method does not behave correctly because swapDown is unimplemented. Implement it and test the modified program.

Exercise 7: Full Heaps

What happens if we try to put too many values into the heap (say, 18 values)?

Fix that problem.

History

Tuesday, 5 April 2005 [Samuel A. Rebelsky]

• Created.