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

}

}

}