Here is lab4.java. This code implements a min heap. Fill in the code for the fol
ID: 3731613 • Letter: H
Question
Here is lab4.java. This code implements a min heap.
Fill in the code for the following methods in the MinHeap class:
• int min(): this method returns the minimum value in the heap, but DOES NOT remove it from the heap.
• int removeMin(): this method returns the minimum value in the heap, and removes it from the heap.
• void insert(int value): this method inserts a new value into the heap. You can assume the array used for representing the heap is not full.
lab4.java:
/*Use this code for lab 4*/
/*Fill in the two functions min, removeMin and insert*/
public class lab4
{
public static void main(String[] args){
int[] a = {50,22,18,14,60,11,32,6,1}; // items to be inserted in the heap
int min;
// build a heap by successively inserting an item
MinHeap h = new MinHeap(100);
for (int i = 0; i < a.length; i++)
h.insert(a[i]);
System.out.print("Heap h built from successive insertion:");
h.printArray();
// now do a few removals
for (int i = 0; i < a.length; i=i+2){
System.out.print("Remove " + h.removeMin() + " from h:");
h.printArray();
}
}
}
class MinHeap{
// array storing items in the min-heap
int[] arr;
int size; // heap size
public MinHeap(int MAXSIZE){
// construct an array and set the size to 0
arr = new int[MAXSIZE];
size = 0;
}
public int min(){
// return the minimum value in the heap (do not remove it from the minHeap)
}
public int removeMin(){
// remove the minimum value from the minHeap return return it
// fill in your code here
}
public void insert(int value){
//insert value into the minHeap
// fill in your code here
}
public void printArray(){
// print the array representation of the heap
for (int i=0; i<size; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
Explanation / Answer
Answer:
Lab4.java:
public class lab4 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {50,22,18,14,60,11,32,6,1}; // items to be inserted in the heap
int min;
// build a heap by successively inserting an item
MinHeap h = new MinHeap(100);
for (int i = 0; i < a.length; i++)
h.insert(a[i]);
System.out.print("Heap h built from successive insertion:");
h.printArray();
// now do a few removals
for (int i = 0; i < a.length; i=i+2){
System.out.print("Remove " + h.removeMin() + " from h:");
h.printArray();
}
}
}
MinHeap.java:
public class MinHeap {
int[] arr;
int size; // heap size
public MinHeap(int MAXSIZE){
// construct an array and set the size to 0
arr = new int[MAXSIZE];
size = 0;
}
public int min(){
// return the minimum value in the heap (do not remove it from the minHeap)
int temp = arr[0];
//Identifying the minimum value
for(int i =0; i<arr.length; i++){
if(arr[i]<temp && arr[i] != 0){
temp = arr[i];
}
}
return temp;
}
public int removeMin(){
int temp = arr[0];
// remove the minimum value from the minHeap return return it
//Identifying the minimum value
for(int i =0; i<arr.length; i++){
if(arr[i]<temp && arr[i] != 0){
temp = arr[i];
}
}
//removing from the array
for(int i=0; i<arr.length; i++){
if(temp == arr[i] ){
for(int j = i; j<arr.length-1; j++){
arr[j] = arr[j+1];
}
}
}
return temp;
}
public void insert(int value){
//insert value into the minHeap
arr[size] = value;
size++;
}
public void printArray(){
// print the array representation of the heap
for (int i=0; i<size; i++){
if(arr[i] != 0){
System.out.print(arr[i]+" ");
}
}
System.out.println();
}
}
Output:
Heap h built from successive insertion:50 22 18 14 60 11 32 6 1
Remove 1 from h:50 22 18 14 60 11 32 6
Remove 6 from h:50 22 18 14 60 11 32
Remove 11 from h:50 22 18 14 60 32
Remove 14 from h:50 22 18 60 32
Remove 18 from h:50 22 60 32
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.