Part 1: The Heap Class [5 points] Create a Java class for the Max Heap data stru
ID: 3686151 • Letter: P
Question
Part 1: The Heap Class [5 points] Create a Java class for the Max Heap data structure. Implement the heap as an array of a fixed capacity. You will need to keep track of the heap size with a private variable. Implement an adequate constructor and a getter method for the size.
Part 2: Insertion [5 points] Implement the insertion method as described in the slides. Make sure the method works properly and that it can handle all situations (like when the capacity of the array is reached).
Part 3: Deletion [5 points] Implement the deletion method as described in the slides. Make sure it works properly and that it can handle situations when the heap has 0, 1, or more elements.
Explanation / Answer
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;
/** Class BinaryHeap **/
class BinaryHeap
{
/** The number of children each node has **/
private static final int d = 2;
private int heapSize;
private int[] heap;
/** Constructor **/
public BinaryHeap(int capacity)
{
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
/** Function to check if heap is empty **/
public boolean isEmpty( )
{
return heapSize == 0;
}
/** Check if heap is full **/
public boolean isFull( )
{
return heapSize == heap.length;
}
/** Clear heap */
public void makeEmpty( )
{
heapSize = 0;
}
/** Function to get index parent of i **/
private int parent(int i)
{
return (i - 1)/d;
}
/** Function to get index of k th child of i **/
private int kthChild(int i, int k)
{
return d * i + k;
}
/** Function to insert element */
public void insert(int x)
{
if (isFull( ) )
throw new NoSuchElementException("Overflow Exception");
/** Percolate up **/
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
/** Function to find least element **/
public int findMin( )
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
/** Function to delete min element **/
public int deleteMin()
{
int keyItem = heap[0];
delete(0);
return keyItem;
}
/** Function to delete element at an index **/
public int delete(int ind)
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
}
/** Function heapifyUp **/
private void heapifyUp(int childInd)
{
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)])
{
heap[childInd] = heap[ parent(childInd) ];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
/** Function heapifyDown **/
private void heapifyDown(int ind)
{
int child;
int tmp = heap[ ind ];
while (kthChild(ind, 1) < heapSize)
{
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
/** Function to get smallest child **/
private int minChild(int ind)
{
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < heapSize))
{
if (heap[pos] < heap[bestChild])
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
/** Function to print heap **/
public void printHeap()
{
System.out.print(" Heap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
}
/** Class BinaryHeapTest **/
class BinaryHeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Binary Heap Test ");
System.out.println("Enter size of Binary heap");
/** Make object of BinaryHeap **/
BinaryHeap bh = new BinaryHeap(scan.nextInt() );
char ch;
/** Perform Binary Heap operations **/
do
{
System.out.println(" Binary Heap Operations ");
System.out.println("1. insert ");
System.out.println("2. delete min");
System.out.println("3. check full");
System.out.println("4. check empty");
System.out.println("5. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
try
{
System.out.println("Enter integer element to insert");
bh.insert( scan.nextInt() );
}
catch (Exception e)
{
System.out.println(e.getMessage() );
}
break;
case 2 :
try
{
System.out.println("Min Element : "+ bh.deleteMin());
}
catch (Exception e)
{
System.out.println(e.getMessage() );
}
break;
case 3 :
System.out.println("Full status = "+ bh.isFull());
break;
case 4 :
System.out.println("Empty status = "+ bh.isEmpty());
break;
case 5 :
bh.makeEmpty();
System.out.println("Heap Cleared ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/** Display heap **/
bh.printHeap();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}