Implement the methods for Heap.java. HeapAPI has info on how to implement the me
ID: 3752091 • Letter: I
Question
Implement the methods for Heap.java. HeapAPI has info on how to implement the methods in heap. Dont modify heapapi it just provides the info.
//HEAPAPI.java do not modify
class HeapException extends Exception
{
/**
* Creates a new instance of HeapException without detail
* message.
*/
public HeapException() { }
/**
* Constructs an instance of HeapException with the specified
* detail message.
* @param msg the detail message.
*/
public HeapException(String msg)
{
super(msg);
}
}
/**
* Describes the basic operations of a heap
* @author Duncan
* @param
* @since 99-99-9999
*/
public interface HeapAPI>
{
/**
* Determine whether the Heap is empty.
* @return this method returns true if the heap is empty;
* otherwise, it returns false if the heap contains at least one item.
*/
boolean isEmpty();
/**
* Inserts an item into the Heap.
* @param item the value to be inserted.
*/
void insert(E item);
/**
* An exception is generated if this method is invoked
* by an empty heap. The maximum/minimum value is removed
* from the heap if the heap is not empty and its effective
* size is reduced by 1.
* @return the maximum (in the case of a maxheap) or the
* minimum (in the case of a minheap) on the heap.
* @throws HeapException when the heap is empty
*/
E remove() throws HeapException;
/**
* An exception is generated if this method is invoked
* by an empty heap
* @return the maximum (in the case of a maxheap) or the
* minimum (in the case of a minheap) on the heap.
* @throws HeapException when the heap is empty
*/
E peek() throws HeapException;
/**
* Gives the size of this heap
* @return the size of the heap; the effective size of the
* heap.
*/
int size();
}
public class Heap> implements HeapAPI {
/**
* A complete tree stored in an array list representing this binary heap
*/
private ArrayList tree;
/**
* A comparator lambda function that compares two elements of this heap when
* rebuilding it; cmp.compare(x,y) gives 1. negative when x less than y 2.
* positive when x greater than y 3. 0 when x equal y
*/
private Comparator cmp;
/**
* Constructs an empty heap using the compareTo method of its data type as the
* comparator
*/
public Heap() {
tree = new ArrayList;
}
/**
* A parameterized constructor that uses an externally defined comparator
*
* @param fn
* - a trichotomous integer value comparator function
*/
public Heap(Comparator fn) {
this.fn = fn;
tree = new ArrayList();
}
public boolean isEmpty() {
return tree.isEmpty();
}
public void insert(E obj) {
// implement this method
}
public E remove() throws HeapException {
// implement this method
}
public E peek() throws HeapException {
// implement this method
}
public int size() {
return tree.size;
}
/**
* Swaps a parent and child elements of this heap at the specified indices
*
* @param place
* an index of the child element on this heap
* @param parent
* an index of the parent element on this heap
*/
private void swap(int place, int parent) {
}
/**
* Rebuilds the heap to ensure that the heap property of the tree is preserved.
*
* @param root
* the root index of the subtree to be rebuilt
* @param eSize
* the size of this tree
*/
private void rebuild(int root, int eSize) {
// implement this method
}
}
Explanation / Answer
Below is your code: -
Heap.java
public class Heap<E extends Comparable<E>> implements HeapAPI<E> {
/**
* A complete tree stored in an array list representing this binary heap
*/
private ArrayList<E> tree;
/**
* Constructs an empty heap
*/
public Heap() {
tree = new ArrayList<E>();
}
@Override
public boolean isEmpty() {
return tree.isEmpty();
}
@Override
public void insert(E obj) {
tree.add(obj);
int place = size() - 1;
int parent = (place - 1) / 2;
while (parent >= 0 && tree.get(place).compareTo(tree.get(parent)) > 0) {
swap(place, parent);
place = parent;
parent = (place - 1) / 2;
}
}
@Override
public E remove() throws HeapException {
if (isEmpty())
throw new HeapException("Heap is empty");
E temp = tree.get(0);
tree.set(0, tree.get(size() - 1));
tree.remove(size() - 1);
rebuild(0, size());
return temp;
}
@Override
public E peek() throws HeapException {
if (isEmpty())
throw new HeapException("Heap is empty");
return tree.get(0);
}
@Override
public int size() {
return tree.size();
}
/**
* Swaps a parent and child elements of this heap at the specified indices
*
* @param place
* an index of the child element on this heap
* @param parent
* an index of the parent element on this heap
*/
private void swap(int place, int parent) {
E temp = tree.get(place);
tree.set(place, tree.get(parent));
tree.set(parent, temp);
}
/**
* Rebuilds the heap to ensure that the heap property of the tree is
* preserved.
*
* @param root
* the root index of the subtree to be rebuilt
* @param eSize
* the size of this tree
*/
private void rebuild(int root, int eSize) {
if (root > 1) {
int child = 2 * root + 1;
if (2 * root + 2 < eSize - 1) {
if (tree.get(child + 1).compareTo(tree.get(child)) > 0) {
child = child + 1;
}
}
if (tree.get(root).compareTo(tree.get(child)) < 0) {
swap(root, child);
rebuild(child, eSize);
}
}
}
}