Write a program that implements a class for a binary minHeap data structure. Imp
ID: 3757730 • Letter: W
Question
Write a program that implements a class for a binary minHeap data structure.
Implement your heap using an array. The minHeap must implement the following functions:
void insert(Event); // the minHeap insert algorithm
void add(Event); // adds the event to the next available array slot, no percolation
Event deleteMin(); // removes and returns the event with the smallest timeOfEvent
boolean isEmpty();
void buildHeap(); // the minHeap buildHeap algorithm
“Event” is a base class for three types of events, Arrival, EndOfService and Termination. Each of these has a class variable, double timeOfEvent, and a function void print() that is called when the object is removed from the queue. These print functions print the class name followed by the class variable, as follows:
Arrival Event at time 24.56.
EndOfService Event at time 50.66.
Termination Event at time 71.78.
All doubles must be printed with two digits before the point and two digits after the point.
The timeOfEvent field is used as the key for all heap operations.
An input must be read from System.in and all output must be to System.out.
Sample Run:
Add Event
Insert Arrival Event
Insert EndOfService Event
Insert Termination Event
Print Array
Build Heap
Delete Min
Quit
Option: 1
Which Event: Arrival
Time : 12.10
Which Event: Arrival
Time: 11.45
Option: 1
Which Event: EndOfService
Time: 11.40
Which Event: Termination
Time: 13.45
Option: 5
Arrival:12.10; Arrival:11.45; EndOfService:11.40; Termination: 13.45
Option : 6
Heap Built
Option: 5
EndOfService :11.40; Arrival:11.45; Arrival:12.10; Termination:13.45
Option: 7
Minimum Deleted
EndOfService Event at time 11.40
Option: 8
Explanation / Answer
import java.util.Scanner;
import java.util.Arrays;
import java.util.NoSuchElementException;
class BinaryHeap
{
private static final int d = 2;
private int heapSize;
private int[] heap;
public BinaryHeap(int capacity)
{
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
public boolean isEmpty( )
{
return heapSize == 0;
}
/** Check if heap is full **/
public boolean isFull( )
{
return heapSize == heap.length;
}
public void makeEmpty( )
{
heapSize = 0;
}
private int parent(int i)
{
return (i - 1)/d;
}
private int kthChild(int i, int k)
{
return d * i + k;
}
public void insert(int x)
{
if (isFull( ) )
throw new NoSuchElementException("Overflow Exception");
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
public int findMin( )
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return heap[0];
}
public int deleteMin()
{
int keyItem = heap[0];
delete(0);
return keyItem;
}
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;
}
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;
}
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;
}
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;
}
public void printHeap()
{
System.out.print(" Heap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
}
public 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");
BinaryHeap bh = new BinaryHeap(scan.nextInt() );
char ch;
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');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.