DATA STRUCTURE ME LAB PROGRAMS-->1. MIN HEAP

 

MIN HEAP

Program Coding:

import java.io.*;

import java.lang.*;

 class heapmin

{

            public int heap[]=new int[20];

            public int size=0;

            public void put(int theelement)

            {

                        if(size == heap.length - 1)

                                    System.out.println("The heap is full");

                        int currentnode=++size;

                        while(currentnode !=1 && heap[currentnode/2]>=theelement)

                        {         

                                    heap[currentnode]=heap[currentnode/2];

                                    currentnode/=2;

                        }

                        heap[currentnode]=theelement;

            }

            public int removeMin()

            {

                        int minelement=heap[1];

                        int lastelement=heap[size--];

                        int currentnode=1;

                        int child=2;

                        while(child <= size)

                        {

                                    if((child < size) && (heap[child]>heap[child+1]))

                                                            child++;

                                    if(lastelement<=heap[child])

                                                break;

                                    heap[currentnode]=heap[child];

                                    currentnode=child;

                                    child *=2;

                        }

                        heap[currentnode]=lastelement;

                        return minelement;

            }

}

class minheap

{

            public static void main(String args[])throws IOException

            {

                        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

                        heapmin obj1=new heapmin();

                        String str1,str2;

                        int a;

                        int b;

                        int c;

System.out.println("1.Insert/put \n 2.Deletemin \n 3.display\n 4.Exit");

 

                        while(true)

                        {

System.out.println("Enter your choice:\t");

                                    str1=br.readLine();

 

                                    a=Integer.parseInt(str1);

 

                                    switch(a)

                                    {

                                    case 1:

                                                System.out.println("Enter the element to be inserted\n");

                                                str2=br.readLine();

                                                b=Integer.parseInt(str2);

                                                obj1.put(b);

                                                break;

                                    case 2:

                                                c=obj1.removeMin();

                                                System.out.println("the root deleted is" + c);

                                                break;

                                    case 3:

                                                System.out.println("The elements are");

                                                for(int i=1;i<=obj1.size;i++)

                                                            System.out.print("\t " + obj1.heap[i]+"\n");

                                                break;

                                    case 4:

                                                System.exit(0);

                                                break;

                                    }

                        }

            }

}

Output:

MIN HEAP:

1.Insert

2.Delete

3.Display

4.Exit

Enter your choice:

1

Enter the element to be inserted:

6

Enter your choice:

1

Enter the element to be inserted:

8

Enter your choice:

1

Enter the element to be inserted:

9

Enter your choice:

2

The root deleted is 6.

Enter your choice:

3

The elements are:

8

9

Enter your choice:

4