Friday, April 9, 2010

ds - insertion and deletion in heap

#include"stdio.h"
#include"conio.h"
#include"alloc.h"
#include"stdlib.h"
#define n 15
struct node
{
int index,parent;
int leaf[n];
};
typedef struct node node;
void heapinsert(node *,int);
void reheapup(node *,int);
void deleteheap(node *); //delete root node
void reheapdown(node *,int);
void display(node);
void main()
{
node heap;
heap.index=-1;
clrscr();
heapinsert(&heap,17);
heapinsert(&heap,52);
heapinsert(&heap,32);
heapinsert(&heap,16);
display(heap);
deleteheap(&heap);
printf("\n");
display(heap);
getch();
}
void heapinsert(node *heap,int x)
{
//heap->parent=0;
if(heap->index==n-1)
{printf("memory overflow");
return;}
heap->index=heap->index+1;
heap->leaf[heap->index]=x;
reheapup(heap,heap->index);
}
void reheapup(node *heap,int x)
{
int t;
if(x!=0)
{
heap->parent=(x-1)/2;
if(heap->leaf[x]>heap->leaf[heap->parent])
{
t=heap->leaf[x];
heap->leaf[x]=heap->leaf[heap->parent];
heap->leaf[heap->parent]=t;
reheapup(heap,heap->parent);
}}
}
void display(node heap)
{
int i,x;
i=heap.index;
for(x=0;x<=i;x++)
printf("%d ",heap.leaf[x]);
}
void deleteheap(node *heap)
{
if(heap->index<0)
{printf("memory underflow");
return;}
heap->leaf[0]=heap->leaf[heap->index];
heap->index--;
reheapdown(heap,0);
}
void reheapdown(node *heap,int root)
{ int t,leftkey,rightkey,largekey,largeindex;
if(root*2+1 <= heap->index)
{
leftkey=heap->leaf[root*2+1];
if(root*2+2<=heap->index)
rightkey=heap->leaf[root*2+2];
else
rightkey=-1;
if(leftkey>rightkey)
{largekey=leftkey;
largeindex=root*2+1; }
else{
largekey=rightkey;
largeindex=root*2+2;
}
if(heap->leaf[root]{
t=heap->leaf[root];
heap->leaf[root]=heap->leaf[largeindex];
heap->leaf[largeindex]=t;
reheapdown(heap,largeindex);
}
}}

No comments:

Post a Comment