Programming Assignment 3
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.
Table of Contents
Download
The skeleton project may be downloaded here.
Submitting
Your project, including all source code, must be submitted by midnight on December 2nd to avoid late penalty. Late submissions will lose 10 points per day late.
Submissions are accepted over email, please use the subject line INFS 519 Program 3 and send to both myself and the TA.
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
orIndexOutOfBoundsException
) when appropriate. - Use an array to store the Integer elements.
Suggestions
- Use private helper methods to lookup the the values of parent and children nodes for a given index.
Project layout
The project has the following directory layout:
- Heap/
- src/
- all program source code
- lib/
- all project library dependencies
- test/
- all test classes
- src/
There may also be a separate directory storing your compiled classes.
Building and testing
Use your IDE to build your code and run the included JUnit tests.