Tuesday, March 22, 2011

WAP to Add and Remove Method In/From Binary Heap Efficiently

import java.io.*;
class heapsort{
int n;
int heap[];
heapsort(int i){
n=i;
heap=new int[i+1];
}
void downheap(int start,int finish)
{
int i=start,l,r,max,temp;
l=2*start;
r=l+1;
if(l<=finish)
{
max=heap[l];
i=l;
if(r<=finish)
if(heap[r]>max)
{
max=heap[r];
i=r;
}
}
if(heap[start] {
temp=heap[start];
heap[start]=heap[i];
heap[i]=temp;
downheap(i,finish);
}
}
void upheap(int start)
{
int temp,par;
if(start>1)
{
par=start/2;
if(heap[par] {
temp=heap[start];
heap[start]=heap[par];
heap[par]=temp;
upheap(par);
}
}
}
void insert(int n,int item)
{
n++;
heap[n]=item;
upheap(n);
}
void heapify(int n)
{
int i,index;
index=n/2;
for(i=index;i>=1;i--)
downheap(i,n);
}

int Delete()
{
int temp;
temp=heap[1];
heap[1]=heap[n];
n--;
downheap(1,n);
return temp;
}
}
class heapsortmethod
{
public static void main(String args[]) throws Exception
{
int temp,n,i,j,k;
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("enter the no. of elements");
n=Integer.parseInt(cin.readLine());
heapsort arr = new heapsort(n);
System.out.println("enter the integers to be sorted");
for(i=1;i<=n;i++)
{
arr.heap[i]= Integer.parseInt(cin.readLine());
}
arr.heapify(n);
System.out.println("the elements indescending order are:");
for(i=1;i<=n;i++)
System.out.println(arr.Delete());
}
}

Only of Add & Remove & Heapify Method

Time Complexity O(logn)
Space Complexity O(1)

No comments :