Homework Assignment 2

I have provided a skeleton of the edu.gmu.cs.heap.Heap class which you should modify and complete. This Heap class will only store Integers, so there's no need to use generic types.

Some basic unit tests are provided to help check your implementation; however, passing these tests does not mean an implementation is correct. There are edge cases not checked by the provided unit tests and this assignment includes requirements not unit-testable.

A binary max-heap is the type of heap we covered in class, more information about this data structure can be found in chapter 10.1 of the book. Pages 511-512 have the definition of a heap and provide examples of what is and isn't a heap.

Table of Contents

Download

The skeleton project may be downloaded here.

Due date

Your project, including all source code, must be submitted by midnight on November 28th to avoid late penalty. Late submissions will lose 10 points per day late.

Submissions are accepted over email.

Requirements

  • Implement all methods in the edu.gmu.cs.heap.Heap class file.
    public Integer max()
    Returns the current maximum element in the heap
    public Integer removeMax()
    Returns and removes the current maximum element in the heap
    public void add(Integer element)
    Add an item to the heap, but make sure to preserve heapness
    public boolean isEmpty()
    Returns true if the heap is empty, false otherwise
    public int size()
    Returns the number of elements in the heap
    private void heapifyDown(int index)
    Reorganize an element at the given index by pushing it down the as necessary
    private void heapifyUp(int index)
    Reorgainze an element at the given index by pushing it up the heap as necessary
  • Use your judgement to throw exceptions (such NoSuchElementException or IndexOutOfBoundsException) when appropriate.
  • Use an array to store the Integer elements.

Suggestions

  • Write private helper methods to help keep any of your methods from becoming too big or complicated.

Project layout

The project has the following directory layout:

  • Heap/
    • src/
      • all program source code
    • build/
      • all program class files
    • lib/
      • all project library dependencies
    • dist/
      • lib/
        • classes packaged in JAR file
    • test/
      • all test classes
    • build.xml

Building and testing

The build.xml file is an ant build file. Ant is a Java build tool that can be used to simplify the process of building, testing, deploying, and running Java programs.

Ant may not already be installed on your computer but can be obtained from here. Some IDEs, such as Eclipse, may include ant. Please feel free to use whatever development tools and IDEs you prefer.

You will also need the JDK installed to compile your code. The JDK can be obtained from here.

To build all source files and create the JAR file:

  • ant dist

The dist task is the default for our build file, so you may also run:

  • ant

If you would like to clean all compiled classes run:

  • ant clean

To run the unit tests:

  • ant test

HTML generated by org-mode 6.35i in emacs 23