Question

Please write down a java program for below instruction.Min-Heap: Construct a Min_Heap from the following set of integers. Remember to use successive adds to arrive at your final Heap. (You do not need to show all the intermediate steps, however, showing those can help in case you make an error somewhere down the line.)1, 19, 7, 5, 6, 42, 21, 13, 56, 78, 29, 3, 14
Remove_Min: Show the result of two successive Remove_Min operations on the heap formed in part a.Perform the following operations on the Min_Heap: add(45)
As you must have noticed the set of integers provided to both the BST and Heap problems were the same. However, the structures formed are vastly different.

What can you say about the relative heights (and therefore the worst-case cost of operations) of the BST as compared to the Heap?

What conclusions are you able to draw regarding the relative efficiency of the 2 data structures? (Remember that log213 = 3.7)

Answer 1

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();

  }

}

Output:

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.