Question
public class Heap { private int currentSize; private int[] heapArray; // Constructors public Heap() { setCurrentSize(0); heapArray = new int[1]; } public Heap(int capacity) {
public class Heap { private int currentSize; private int[] heapArray; // Constructors public Heap() { setCurrentSize(0); heapArray = new int[1]; } public Heap(int capacity) { setCurrentSize(0); heapArray = new int[capacity + 1]; } // Heap Operations public int[] buildHeap(int[] array) { // Builds the heap from an array that you have provided // IMPLEMENT THIS METHOD // ... // percolateDown(hole); } private void percolateDown(int hole) { // Organizes the elements of the heap and percolate down the elements for not violating heap properties // IMPLEMENT THIS METHOD // ... } public int getMinValue() { // Returns the min (root) of the binary min heap
// IMPLEMENT THIS METHOD // ... } public int getHeight() { // Returns the height of the binary min heap // IMPLEMENT THIS METHOD // ... } public boolean checkMinHeap(int[] array) { // Returns TRUE if given array is a binary min heap, FALSE otherwise // IMPLEMENT THIS METHOD // ... } public void insert(int value) { // Inserts an integer element to the binary min heap if(currentSize == heapArray.length - 1) enlargeArray(heapArray.length + 1); int hole = ++currentSize; percolateUp(value, hole); } private void percolateUp(int value, int hole) { // Organizes the elements of the heap and percolate up the elements for not violating heap properties for(heapArray[0] = value; Integer.compare(value, heapArray[hole / 2])
public void setCurrentSize(int currentSize) { this.currentSize = currentSize; }
public int[] getHeapArray() { return heapArray; }
public void setHeapArray(int[] heapArray) { this.heapArray = heapArray; } }
public class Main {
public static void main(String[] args) { // Instantiate a heap // ... // Build the heap with using insert method for some numbers like 52, 25, 40, 2, 10, etc. // insert(52); // insert(25); // . . // . . // . . // Print the heap that you have created // ... // Get min value of the heap that you have created // ... // Get height of the heap that you have created // ... int[] arrayC = {90, 70, 2, 15, 65, 164, 18, 40, 58, 77, 303}; // Check if arrayC[] is a heap or not with using checkMinHeap() method // ... // Use arrayC[] for building the heap again with buildHeap() method this time and print it // ... }
}
Download Heap.java and Main.java from Blackboard. Create a Java Project; put all downloaded Java files in the same package. In this assignment you are already given an array implementation of a Heap. You need to modify both Heap.java and Main.java files. 1. Instantiate a new Heap object in the main function. (5 pts] 2. Heap class has an insert(int value) method which inserts the given value to the heap. Use that method to build your heap with random numbers. You can use any value to test whether the method works properly or not. (10 pts] 3. Print the elements that you have inserted using the method printHeap (). 15 pts) 4. Implement getMinValue () method which returns the minimum element of the heap. Use it and print the minimum value. (10 pts) 5. Implement getHeight () method which returns the height of the heap. Use it and print the height of the heap. (10 pts] 6. Implement checkMinHeap (int[] array) to check if the given array arrayC[] represents a binary min heap or not. If it is a heap, then your method should return TRUE; FALSE if it is not. [10 pts) 7. Implement the buildHeap (int value) method this time which builds a binary min heap from the given array arrayC[]. (20 pts] 7.1. You will need to implement percolate Down (int hole) helper method for buildHeap method to work. It moves down the hole to the correct position without violating the heap order property. (25 pts] 8. Print the heap elements using printHeap () again. (5 pts] 9. Submit your Heap.java and Main.java files through BlackboardStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started