MIN HEAP

AIM

To implement the min heap structure with insert and delete minimum operation using Java program

  

ALGORITHM

Step 1:              start the program by creating function with min heap property

Step 2:              two functions namely insert() and deletemin() are created

Step 3:              the insert() is used to insert new element in the tree structure with heap property.

Step 4:              The deletemin() is used to delete the minimum element which is usually a root node.

Step 5:              The two operations are performed satisfying heapness and completeness property.

Step 6:              End of the program.

PROGRAM:

MIN HEAP

import java.io.*;

class heapalg

{

    int maxsize=100,size;

    int[] h=new int[maxsize];  

    public int leftchild(int i)

    {

          return 2*i;      

    }

    public int rightchild(int i)

    {

          return 2*i + 1;

    }   

    public int parent(int i)

    {

          return i/2;

    }

    public boolean isleaf(int i)

    {

       return ((i<=size) && (i>size/2));     

    }

    public void swap(int i,int j)

    {

          int t;

          t=h[i];h[i]=h[j];h[j]=t;

    }

    public void display()

    {

         System.out.println("The heap elements are:"+"\n");

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

            System.out.println("\n"+h[i]);

    }    

    public void insert()  

    {     

        size++;

        if(size>maxsize)

          System.out.println("Heapfull");

        else

        {

           try

           {

              System.out.println("Enter the element:");

              DataInputStream din=new DataInputStream(System.in);

              h[size]=Integer.parseInt(din.readLine());

           }

           catch(Exception e){}

           insertelt(size);

        }

    }

    public void insertelt(int  i)  

    {

  while ((h[parent(i)]>h[i]))

{

            int par=parent(i);

            swap(par,i);

            i=par;

         }

    }

    public void delete()

    {      

          if(size==0)

            System.out.println("Heapempty");

           else

           {

            System.out.println("The deleted min elt:"+h[1]);

            h[1]=h[size--];

            if(size!=0)

              percolate(1);

           }     

     }

   public void percolate(int i)

   {

       while(!isleaf(i))

       {

          int small=leftchild(i);    

          if( (small<size)&& h[small] > h[small+1])

             small+=1;

          if(h[small] < h[i]) 

                swap(small,i);

          i=small;

      }

  }

MIN HEAP

Heap.java

import java.io.*;

class minheap {

private int[] Heap;

private int maxsize;

private int size;

public minheap(int max) {

maxsize = max;

Heap = new int[maxsize];

size = 0 ;

Heap[0] = Integer.MIN_VALUE;

}

private int leftchild(int pos) {

return 2*pos;

}

private int rightchild(int pos) {

return 2*pos + 1;

}

private int parent(int pos) {

return  pos / 2;

}

private boolean isleaf(int pos) {

return ((pos > size/2) && (pos <= size));

}

private void swap(int pos1, int pos2) {

int tmp;

tmp = Heap[pos1];

Heap[pos1] = Heap[pos2];

Heap[pos2] = tmp;

}

public void insert(int elem) {

size++;

Heap[size] = elem;

int current = size;

while (Heap[current] < Heap[parent(current)]) {

swap(current, parent(current));

current = parent(current);

}

}

public void print() {

int i;

for (i=1; i<=size;i++)

System.out.print(Heap[i] + " ");

System.out.println();

}

public int removemin() {

swap(1,size);

size--;

if (size != 0)

pushdown(1);

return Heap[size+1];

}

private void pushdown(int position) {

int smallestchild;

while (!isleaf(position)) {

smallestchild = leftchild(position);

if ((smallestchild < size) && (Heap[smallestchild] > Heap[smallestchild+1]))

smallestchild = smallestchild + 1;

if (Heap[position] <= Heap[smallestchild]) return;

swap(position,smallestchild);

position = smallestchild;

}

}

}

class Heap{

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

{

System.out.println("--MinHeap--");

int item,f,choice=1;

minheap m=new minheap(100);

System.out.println("1. Insertion");

System.out.println("2. Deletion ( min element)");

System.out.println("3. Exit..");

while(choice<3)

{

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

InputStreamReader in1=new InputStreamReader(System.in);

BufferedReader br1=new BufferedReader(in1);

String s1=br1.readLine();

choice=Integer.parseInt(s1);

switch(choice)

{

case 1:

System.out.print("\nEnter the no of items to be inserted:");

int size=Integer.parseInt(br1.readLine());

for(int i=0;i<size;i++)

{

System.out.print("\nEnter the item to be inserted:");

String s2=br1.readLine();

item=Integer.parseInt(s2);

m.insert(item);

}

break;

case 2:

int itemd=m.removemin();

System.out.println("The deleted item is :  "+itemd);

break;

case 3:

break;

}

m.print();

}

}

}