// File: BinaryHeap.java

// Author: Rita Ester

// (your name here)

// Date: Mar.17, 2018

// Description: Binary heap class for CSCI 225 Ass.5

public class BinaryHeap {

private PrioItem[] heapArray;

private int heapArraySize; // length of the heapArray

private int heapSize; // current number of items in the heap

// private methods

// rebuilds an array of PrioItem not in partial order (stored in the heapArray) into a heap.

// PRE: heapArray not in partial order

// POST: heapArray in partial order of a Max Heap.

private void heapify(){

// to be completed

}

// Fixes partial ordering from i to root, swaps i with parent if heapArray[i] > parent.

// Use the compareTo method to compare objects of the PrioItem class.

// PRE: heapArray not in partial order

// PARAM: i is index to be sifted up from

// POST: heapArray in partial order of a Max Heap.

private void siftUp(int i){

// to be completed

}

// Fixes partial ordering from i to leaf, swaps i with parent if heapArray[i]

// Use the compareTo method to compare objects of the PrioItem class.

// PRE: heapArray not in partial order

// PARAM: i is index to be sifted down from

// POST: heapArray in partial order of a Max Heap.

private void siftDown(int i){

// to be completed

}

// Recursively prints the heap structure as described

// in the assignment

// PRE:

// PARAM: node is the current index, level is the depth of node

// POST:

private void printHeapSideWays(int node, int level){

// to be completed

}

// public methods

// Default constructor

// PRE:

// POST: creates and empty heap of size 10

public BinaryHeap(){

heapArraySize = 10;

heapArray = new PrioItem[heapArraySize];

heapSize = 0;

}

// Constructor

// PRE:

// PARAM: n - size of the heap

// POST: creates and empty heap of size n

public BinaryHeap(int n){

heapArraySize = n;

heapArray = new PrioItem[heapArraySize];

heapSize = 0;

}

// Inserts an item into the heap, the heapArray grows array if heap is full

// PRE:

// PARAM: str string to be inserted,

// priority to be inserted.

// POST: inserts a new item into the heap, maintaining the heap

// properties.

public void insert(String str, int priority){

PrioItem newItem = new PrioItem(str, priority);

// to be completed

// if heapArray is full, grow it to double the size.

// insert

}

// Removes root of heap and returns its String item,

// throws exception if heap is empty

// PRE: heapArray is not empty

// POST: removes and returns root, maintaining the heap

// properties

public String removeMax() throws Exception{

//to be completed

return "";

}

// returns the root's String item,

// throws exception if heap is empty

// PRE: heapArray is not empty

public String getMax() throws Exception {

// to be completed

return "";

}

// merges this heap with the other heap.

// heapArray needs to grow if it is too small to hold both heaps.

public void mergeHeap(BinaryHeap other){

// to be completed.

}

// Returns the size of the heap

public int size(){

return heapSize;

}

// Returns true if heap is empty

// PRE:

// POST: returns true if size == 0

public boolean isEmpty(){

return heapSize == 0;

}

// Displays the contents of the heap

// Calls recursive method with initial parameters

public void printHeap(){

printHeapSideWays(0, 0);

}

}

----------------------------------------------------------------------------------------------------------------------------

// File: CSCI225Ass5Driver.java

// Author: Rita Ester

// (your name here)

// Date: Mar. 17, 2018

// Description: Test driver for CSCI 225 Ass5

import java.util.Random;

public class CSCI225Ass5Driver {

static Random r = new Random(System.nanoTime());

static final int numitems = 15;

static final int maxvalue = 100;

public static void main(String[] args)

{

HeapTest1();

HeapTest2();

HeapTest3();

}

public static void HeapTest1()

{

BinaryHeap hp = new BinaryHeap();

// tests insert

hp.insert("aaa",7);

hp.insert("bbb",1);

hp.insert("ccc",3);

hp.insert("ddd",13);

hp.insert("eee",1);

hp.insert("fff",4);

System.out.println("Heap: ");

hp.printHeap();

System.out.println("");

// tests removeMax()

while (!hp.isEmpty())

{

try

{

//tests getMax()

System.out.println("Priority String: " + hp.getMax());

System.out.println("Removed: " + hp.removeMax());

System.out.println("Heap: ");

hp.printHeap();

System.out.println("");

}

catch (Exception e)

{

System.out.println(e.getMessage());

}

}

}

public static void HeapTest2() {

BinaryHeap hp = new BinaryHeap();

// tests the expanding of the heap array in insert(...)

for (int i = 0; i

{

hp.insert("AA", r.nextInt(2*numitems));

}

// tests the exception in removeMax()

for (int i = 0; i

try{

System.out.println("Removed: " + hp.removeMax());

System.out.println("Heap: ");

hp.printHeap();

System.out.println("");

}

catch (Exception e){

System.out.println(e.getMessage());

}

}

}

public static void HeapTest3() {

BinaryHeap hp1 = new BinaryHeap();

// tests insert

hp1.insert("aaa",7);

hp1.insert("bbb",1);

hp1.insert("ccc",3);

hp1.insert("ddd",13);

hp1.insert("eee",1);

hp1.insert("fff",4);

System.out.println("Heap hp1: ");

hp1.printHeap();

System.out.println("");

BinaryHeap hp2 = new BinaryHeap();

hp2.insert("AAA",17);

hp2.insert("BBB",11);

hp2.insert("CCC",3);

hp2.insert("DDD",123);

hp2.insert("EEE",1);

hp2.insert("FFF",4);

System.out.println("Heap hp2: ");

hp2.printHeap();

System.out.println("");

// tests mergeHeap(...)

hp2.mergeHeap(hp1);

System.out.println("Merged Heap: ");

hp2.printHeap();

System.out.println("");

}

}

------------------------------------------------------------------------------------------------------------------------------------------------

// class used to store a string and its priority.

public class PrioItem implements Comparable{

private String item;

private int priority;

//Constructor

public PrioItem(String it, int prio){

item = it;

priority = prio;

}

// Accessor

public int getPriority(){

return priority;

}

// Mutator

public void setPriority(int prio){

priority = prio;

}

// Accessor

public String getItem(){

return item;

}

// Mutator

public void setItem(String it){

item = it;

}

public String toString(){

return "["+item + ","+ priority +"]";

}

//implements the compareTo method of the interface

public int compareTo(PrioItem prItem){

return this.priority - prItem.getPriority();

}

}

Binary Heaps In this assignment, you are to implement various methods of a BinaryHeap class. This class is using an array to store the heap. The incomplete class BinaryHeap.java, a testdriver and the PrioItem class for storing a String and its priority value are provided. The heap must satisfy the max heap properties for the priority values Methods to be completed (19 marks) siftUp is responsible for fixing the partial ordering of the heap from its index parameter up to the root index 0. For a max heap, the partial ordering property is that a node's value is equal or greater than the priority values of its children. siftDown is responsible for fixing the partial ordering of the heap from its index parameter down to the leaves. For a max heap, the partial ordering property is that a node's value is equal or greater than the priority values of its children. heapify builds an array into a heap, starting at the non-leaf nodes, as explained in the lecture notes. (2) insert places an item into the heap according to its priority value. If the heap array is full it should be expanded to double its size before inserting. removeMax returns the String of the item with the highest priority and removes the item from the heap If the heap is empty, this method with throw an exception. getMax returns the String of the item with the highest priority. If the heap is empty, this method with throw an exception. mergeHeap merges the existing heap with another one, entered as parameter. printHeapSideWays will print the contents of the heap array as a tree in a reversed in-order way, as seen for binary trees. Here is an example: 9 7 4 1 Binary Heaps In this assignment, you are to implement various methods of a BinaryHeap class. This class is using an array to store the heap. The incomplete class BinaryHeap.java, a testdriver and the PrioItem class for storing a String and its priority value are provided. The heap must satisfy the max heap properties for the priority values Methods to be completed (19 marks) siftUp is responsible for fixing the partial ordering of the heap from its index parameter up to the root index 0. For a max heap, the partial ordering property is that a node's value is equal or greater than the priority values of its children. siftDown is responsible for fixing the partial ordering of the heap from its index parameter down to the leaves. For a max heap, the partial ordering property is that a node's value is equal or greater than the priority values of its children. heapify builds an array into a heap, starting at the non-leaf nodes, as explained in the lecture notes. (2) insert places an item into the heap according to its priority value. If the heap array is full it should be expanded to double its size before inserting. removeMax returns the String of the item with the highest priority and removes the item from the heap If the heap is empty, this method with throw an exception. getMax returns the String of the item with the highest priority. If the heap is empty, this method with throw an exception. mergeHeap merges the existing heap with another one, entered as parameter. printHeapSideWays will print the contents of the heap array as a tree in a reversed in-order way, as seen for binary trees. Here is an example: 9 7 4 1