Execute program maxHeap.java and heapApplication.java(Attached Screenshot): Insert the nodes listed in 95 77 43 66 64 25 44 11 10 47 to the heap. Show screenshot. Display the heap array and compare it with the array in 95 77 43 66 64 25 44 11 10 47 . What do you find out? Max Heap import java.util.*; public class maxHeap { public int heapSize, capacity; public int[] Arr; public maxHeap(int cap) { heapSize = 0; capacity = cap; Arr = new int[cap]; } public void heapify(int parent) { int Lson, Rson, largest, temp; Lson = 2 * parent + 1; Rson = 2 * parent + 2; /* find the largest among A[parent], A[lson] and A[rson] */ if ( Lson <= heapSize - 1 && Arr[Lson] > Arr[parent] ) { largest = Lson; } else { largest = parent; } if (Rson <= heapSize - 1 && Arr[Rson] > Arr[largest] ) { largest = Rson; } if (largest != parent) { temp = Arr[parent]; Arr[parent] = Arr[largest]; Arr[largest] = temp; heapify(largest); } } public void buildHeap() { for (int i = (heapSize - 2) / 2; i >= 0; i--) { heapify(i); } } public void displayHeap() { System.out.println("heapArray: "); // array format for(int m=0; m 0) // for each heap item { if(column == 0) // first item in row? for(int k=0; k 0 && Arr[parent] < item) { Arr[i] = Arr[parent]; i = parent; parent = (i - 1) / 2; } Arr[i] = item; } public void heapSort() { int temp; // buildHeap(); int keepSize = heapSize; for (int i = heapSize - 1; i >= 1; i--) { temp = Arr[heapSize-1]; Arr[heapSize - 1] = Arr[0]; Arr[0] = temp; heapSize = heapSize - 1; heapify(0); } heapSize = keepSize; printHeap(); } }
Execute program maxHeap.java and heapApplication.java(Attached Screenshot):
- Insert the nodes listed in
to the heap. Show screenshot.95
77
43
66
64
25
44
11
10
47
- Display the heap array and compare it with the array in
. What do you find out?95
77
43
66
64
25
44
11
10
47
Max Heap
import java.util.*;
public class maxHeap
{
public int heapSize, capacity;
public int[] Arr;
public maxHeap(int cap)
{
heapSize = 0;
capacity = cap;
Arr = new int[cap];
}
public void heapify(int parent)
{
int Lson, Rson, largest, temp;
Lson = 2 * parent + 1;
Rson = 2 * parent + 2;
/* find the largest among A[parent], A[lson] and A[rson] */
if ( Lson <= heapSize - 1 && Arr[Lson] > Arr[parent] )
{
largest = Lson;
}
else
{
largest = parent;
}
if (Rson <= heapSize - 1 && Arr[Rson] > Arr[largest] )
{
largest = Rson;
}
if (largest != parent)
{
temp = Arr[parent];
Arr[parent] = Arr[largest];
Arr[largest] = temp;
heapify(largest);
}
}
public void buildHeap()
{
for (int i = (heapSize - 2) / 2; i >= 0; i--)
{
heapify(i);
}
}
public void displayHeap()
{
System.out.println("heapArray: "); // array format
for(int m=0; m<heapSize; m++)
if(Arr[m] != 0)
System.out.print( Arr[m] + " ");
else
System.out.print( "-- ");
System.out.println();
// heap format
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0; // current item
String dots = "...............................";
System.out.println(dots+dots); // dotted top line
while(heapSize > 0) // for each heap item
{
if(column == 0) // first item in row?
for(int k=0; k<nBlanks; k++) // preceding blanks
System.out.print(' ');
// display item
System.out.print(Arr[j]);
if(++j == heapSize) // done?
break;
if(++column==itemsPerRow) // end of row?
{
nBlanks /= 2; // half the blanks
itemsPerRow *= 2; // twice the items
column = 0; // start over on
System.out.println(); // new row
}
else // next item on row
for(int k=0; k<nBlanks*2-2; k++)
System.out.print(' '); // interim blanks
} // end for
System.out.println("\n"+dots+dots); // dotted bottom line
} // end displayHeap()
public void printHeap()
{
for (int i = 0; i <= heapSize - 1; i++)
{
System.out.println(Arr[i]);
}
}
public int extractMax()
{
if (heapSize == 0)
{
System.out.println("Heap is empty");
return -9999999;
}
else
{
int max = Arr[0];
Arr[0] = Arr[heapSize - 1];
heapSize = heapSize - 1;
heapify(0);
return max;
}
}
public void heapInsert(int item)
{
if(heapSize == capacity){
System.out.println("The heap is full!");
return;
}
int parent;
heapSize = heapSize + 1;
int i = heapSize - 1;
parent = (i - 1) / 2;
while (i > 0 && Arr[parent] < item)
{
Arr[i] = Arr[parent];
i = parent;
parent = (i - 1) / 2;
}
Arr[i] = item;
}
public void heapSort()
{
int temp;
// buildHeap();
int keepSize = heapSize;
for (int i = heapSize - 1; i >= 1; i--)
{
temp = Arr[heapSize-1];
Arr[heapSize - 1] = Arr[0];
Arr[0] = temp;
heapSize = heapSize - 1;
heapify(0);
}
heapSize = keepSize;
printHeap();
}
}
![import java.util.;
public class heapApplication
public static vold main(String args[])
Random rnd new Random();
System.out.println("Enter the capacity of the heap: ");
int size = Integer.parseInt(new Scanner(System.in).nextLine());
maxHeap H = new maxHeap(size); // create a new heap H
for(int i = 0; i<15; i++){
int x = rnd.nextInt(1001);
H. heapInsert(x);
System.out.printf("%d ", x);
H.displayleap();
System.out.println("Enter 1 for extractMax, 2 for heapInsert, 3 Heap Sort, 4 Exit");
int s = Integer.parseInt(new Scanner(System.in).nextLine());
while (s == 1 || s == 2 || s==3 || s==4)
if (s 1)
int max = H.extractMax();
if (max != -9999999)
System.out.println("The maximum element is:");
System.out.println(max);
System.out.println("The elements in the array after extracting the max:");
H.displayleap();
};
};
if (s = 2)
System.out.println("Insert a new item to the heap:");
int newItem = Integer.parseInt (new Scanner(System.in).nextLine());
H. heapInsert(newItem);
System.out.println("The elements in the array after inserting the new item: ");
H.displayleap();
};
if (s == 3)
int ans;
System.out.println("Warning: After heap sort, current heap will not be restored and the application will end!");
System.out.println("Continue with sorting? 1 for yes, 2 for no: \n");
ans = Integer.parseInt(new Scanner(System.in).nextLine());
if(ans1){
H. heapSort();
System.out.println("Goodbye!");
return;
};
if (s == 4)
{
System.out.printin("Goodbye!");
return;
};
System.out.println("Enter 1 for extractMax, 2 for heapInsert, 3 Heap Sort, 4 Exit");
s = Integer.parseInt(new Scanner(System.in).nextLine());](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F3ded9074-643d-40d8-825c-f0dff7af7ebf%2Ff2475972-3af4-4ffd-800b-352814c897ee%2Fp82cwnb_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
