Answer:
Following are the program in the Java Programming Language.
//define class
class Heap{
//set private integer data type array variable
private int a[];
//set two private integer data type variables
private int s,capacity;
//define private void function for down heap
private void downheap(int indx) {
//set if conditional statement
if(indx>=s)return;
//set integer type variable and initialize
int lft=2*indx+1;
int rgt=2*indx+2;
int min=indx;
//set the if-else if conditional statement
if(rgt<=s&&a[rgt]<a[indx])
min=rgt;
else if(lft<=s&&a[lft]<a[min])
min=lft;
//check index is not equal to min
if(indx!=min){
//perform swapping
int temp=a[indx];
a[indx]=a[min];
a[min]=temp;
downheap(min);
}
}
//define private void type function for upheap
private void upheap(int indx) {
if(indx==0)return;
int parent=(indx-1)/2;
if(a[indx]<a[parent]) {
int temp=a[indx];
a[indx]=a[parent];
a[parent]=temp;
upheap(parent);
}
}
public Heap(int q) {
a=new int [q];
s=0;
capacity=q;
}
public int _size () {
return s;
}
public int minLookup() {
if(s>0)return a[0];
return 0;
}
public int remove() {
int data=a[0];
a[0]=a[s-1];
s--;
downheap(0);
return data;
}
public void add (int data) {
if(s>=capacity)return;
a[s++] = data;
upheap(s-1);
}
public void print_heap() {
System.out.print("Heap : ");
for(int i=0;i<s;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
}
//define class to define main method
public class Main {
//main method
public static void main(String srgs[]) {
//cretae class object
Heap heap = new Heap(20);
//call function through object with argument list
heap.add(1);
heap.add(19);
heap.add(7);
heap.add(5);
heap.add(6);
heap.add(42);
heap.add(21);
heap.add(13);
heap.add(56);
heap.add(78);
heap.add(29);
heap.add(3);
heap.add(14);
heap.print_heap();
//print the Output and remove the minimum element
System.out.println("Minimum element : "+heap.remove());
heap.print_heap();
System.out.println("minimum element : "+heap.remove());
heap.add(45);
heap.print_heap();
}
}
<u>Output:</u>
Heap : 1 5 3 13 6 7 21 19 56 78 29 42 14
Minimum element : 1
Heap : 3 5 7 13 6 14 21 19 56 78 29 42
Minimum element : 3
Heap : 7 5 21 13 6 14 42 19 56 78 29 45
Explanation:
Here, we define a class "Heap" inside the class.
- Set private integer data type array variable.
- set private two integer data type variables.
- Then, we define private void type function "downheap()" for down heap and pass an integer data type argument list in its parameter "indx".
- Then, we define private void type function "upheap()" for upper heap and pass an integer data type argument list in its parameter "indx".
- Define constructor of the class for the capacity pf the array list.
- Define void type function "add()" for adding elements in heap.
- Define void type function "print_heap()" to print the heap.
Finally, we define class to define main function and we create the object of the class "Heap" then, call all the functions through the class object abd print the output.