1 Requirements 1. Design and implement a Binary Heap class that must support \"i
ID: 3701548 • Letter: 1
Question
1 Requirements 1. Design and implement a Binary Heap class that must support "insert" and "deleteMi" 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
/** * 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 && tmpRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.