Must be in JAVA 1. Design and implement a Binary Heap class that must support \"
ID: 3706706 • Letter: M
Question
Must be in JAVA
1. Design and implement a Binary Heap class that must support "insert" and "deleteMin" operations 2. Design and implement a driver (the main method) that does the following: (a) Creates an array that contains a list of 4099 integers, in a random order, between 0 to to 4098. (b) insert, into the first binary heap that is initially empty, the numbers in the array sequentially from the start to the end (c) Initialize the second empty binary heap (d) Enter a forever while loop to do the following i. Collect the first timestamp ii. Call "deleteMin" to remove the smallest value from the first heap, and display "The process with a priority of %d is now scheduled to run!" iii. For the removed value, change it to a random value between 0 and 4098. iv. Call " Insert" to insert the removed value (now changed to a different value in the previous step) to the second heap, and display "The process with a priority of %d has run out of its timeslice!" v. When the first heap becomes empty, collect the second times- tamp, compute the of the two timestamps, and display "It took ? msecs for all processes to run out of their timeslices." Please press " Enter to start the next round!" vi. When "Enter" is pressed, swap the two heaps, and continue the oopExplanation / Answer
Implemenetation of binary Heap given beloiw:
* Binary Heap
*/
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 */
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");
/* 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');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.