You are going to build in Java a Binary Heap (BHEAP). It will be done by building a maximum binary heap (BHEAP) with the numerically largest priority at the root of the tree.
Once your basic BHEAP is done and working properly, you will add to the ADT a Heap Sort function. The sort is passed an array of doubles as parameter, and produces an array of doubles as return value with the doubles sorted from smallest to largest (smallest double in array slot 0).
Hand in your code as per the instructions under
Assignment 3 in Sakai.
For uniformity, to aid grading, you must write your program with these specific structures. Note that this time there is one interface for the BHEAP ADT, and that the heap sort is a method within the BHEAP.
package MaxBinHeap_A3;
public interface Heap_Interface {
/*
Interface: The BHEAP will provide this collection of operations:
insert
in: a double (assume no duplicates will be inserted)
return: void
delMax
in: nothing
return: void
getMax
in: nothing
return: a double
size
in: nothing
return: integer 0 or greater
clear
in: nothing
return: void
this sets the heap to the state it has when first created... no elements
in the heap array, size 0, next useable array slot is 1.
build
in: array of double that needs to be in the heap
return: void
(assume for a build that the bheap will start empty)
sort
in: array of double
return: array of double
getheap:
in: nothing
return: array of double (the internal array that holds the heap elements
(this will be called by the grader to examine your data structure)
*/
// ADT operations
void insert(double element);
void delMax();
double getMax();
void clear();
int size();
void build(double [] elements);
double[] getHeap();
double[] sort(double[] elements);
}
package MaxBinHeap_A3;
public class MaxBinHeap implements Heap_Interface {
private double[] array; //load this array
private int size;
private static final int arraySize = 10000; //Everything in the array will initially
//be null. This is ok! Just build out
//from array[1]
public MaxBinHeap() {
this.array = new double[arraySize];
array[0] = Double.NaN; //0th will be unused for simplicity
//of child/parent computations...
//the book/animation page both do this.
}
//Please do not remove or modify this method! Used to test your entire Heap.
@Override
public double[] getHeap() {
return this.array;
}
// add your method implementstions
}
package MaxBinHeap_A3;
public class MaxBinHeap_Playground {
public static void main(String[] args) {
// Add more tests as methods and call them here!!
TestBuild();
System.out.println();
TestSort();
}
public static void TestBuild() {
// constructs a new maxbinheap, constructs an array of double,
// passes it into build function. Then print collection and heap.
MaxBinHeap mbh = new MaxBinHeap();
double[] collection = new double[] { 3, 8, 2, 1, 7, 4, 6, 5 };
mbh.build(collection);
printHeapCollection(collection);
printHeap(mbh.getHeap(), mbh.size());
}
public static void TestSort() {
// constructs a new maxbinheap, constructs an array of double, passes
// it into heapsort function. Then print collection and sorted array.
MaxBinHeap mbh = new MaxBinHeap();
double[] collection = new double[] { 3, 8, 2, 1, 7, 4, 6, 5 };
double[] sorted = mbh.sort(collection);
printSortCollection(collection);
printHeap(mbh.getHeap(), mbh.size());
printArray(sorted);
}
public static double[] charsToDoubles(char[] chars) {
double[] ret = new double[chars.length];
for (int i = 0; i < chars.length; i++) {
ret[i] = charToInt(chars[i]);
}
return ret;
}
public static int charToInt(char c) {
return c - 'a';
}
public static void printHeapCollection(double[] e) {
// this will print the entirety of an array of doubles you will pass
// to your build function.
System.out.println("Printing Collection to pass in to build function:");
for (int i = 0; i < e.length; i++) {
System.out.print(e[i] + "\t");
}
System.out.print("\n");
}
public static void printHeap(double[] e, int len) {
// pass in mbh.getHeap(),mbh.size()... this method skips over unused 0th
// index....
System.out.println("Printing Heap");
for (int i = 1; i < len + 1; i++) {
System.out.print(e[i] + "\t");
}
System.out.print("\n");
}
public static void printSortCollection(double[] e) {
// this will print the entirety of an array of doubles you will pass
// to your build function.
System.out.println("Printing Collection to pass in to heap sort function:");
for (int i = 0; i < e.length; i++) {
System.out.print(e[i] + "\t");
}
System.out.print("\n");
}
public static void printArray(double[] array) {
System.out.println("Printing Array");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + "\t");
}
System.out.print("\n");
}
}
package MaxBinHeap_A3;
import gradingTools.comp410s20.assignment3.testcases.Assignment3Suite;
public class RunTests {
public static void main(String[] args){ //runs Assignment 3 oracle tests
Assignment3Suite.main(args);
}
}
Ordering is done based on the doubles as priorities. In the test data we use, the double priorities will be unique -- there will be no duplicate values.
This operation returns a double. It does NOT alter the heap. The heap has the same elements in the same arrangement after as it did before. If getMax is done on an empty heap, return Double.NaN .
This operation removes the root element from the heap. The size of the heap goes down by 1 (if the heap was not already empty). If delMax is done on an empty heap, treat it as a no-op... i.e., do nothing other than return void.
The build operation should start with an empty heap. This means empty the internal heap array first before anything else. It receives an array of elements (doubles) as input. The effect is to produce a valid heap that contains exactly those input elements. This means when done the heap will have both a proper structure and will exhibit heap order.
Build is not the same as doing an insert for every element in the array. It is the special O(N) operation from the text (and shown in class) that starts with placing all elements into the heap array with no regard to heap order. You then go to the parent of the last node, and bubble down as needed. Go to the next node back towards the root, bubble down as needed. Repeat until you have done the root.
The size operation simply returns the count of how many elements are in the heap. It should be 0 if the heap is empty, and always return a 0 or greater.
This method will use the head to sort... i.e., heap sort. It will receive an array of elements (double) is some order and it will return an array containing those same elements in increasing order with the smallest element in array slot 0. The sort will be done by emptying the interal heap array and then building a valid heap from the elements in the input array. Then repeated delMax() operations should be done to extract the elements in sorted order, and those elements put into the return array. Pay attention to the fact that you have max bin heap but need the sort to be increasing smallest to largest.
For testing, use the animation page given in class to get test cases and examples of correct behavior. Make sure your code is doing the same.
Their is no specific output or format required for this assignment. We assume you will use the "print" capability provided (and potentially expand on it) to test your code beyond the scope of the oracle.
Furthermore, please note that just because the Oracle gives you 100, you are not guaranteed any specific grade on the assignment. We do try to put as many things as we can in there edge-case wise, but testing your programs is your responsibility. The main goal of the Oracle is to provide some direction. However, it is not the end-all be-all determiner of correctness. Please do not use this tool as a crutch.
Follow the instructions given in the assignment on Sakai.