Heap

Add a value to the min heap:

n=0; // initial value, before add any value

void AddToTheheap(long h1)
{
long root,up,k;

value[n] = h1;
n++;

root=n-1;
while(1)
{
if(root==0)
break;
up=(root-1)/2;

if(value[up]>value[root])
{
k=value[root];
value[root]=value[up];
value[up]=k;
root=up;
}
else
break;
}
}

Get a value from the min heap
taken value = value[0];
then call Reheap();

void Reheap()
{
long root,left,right,k;

value[0]=value[n-1];
n=n-1;
root=0;

while(1)
{
left=2*root +  1;
right=2*root+ 2;

if(left>=n && right>=n)
break;

if(right>=n)
{
if(value[root]>value[left])
{
k=value[root];
value[root]=value[left];
value[left]=k;
root=left;
}
break;
}
else
{
if(value[left]<value[root]&&value[left]<=value[right])
{
k=value[root];
value[root]=value[left];
value[left]=k;
root=left;
}
else if(value[right]<value[root]&&value[right]<=value[left])
{
k=value[root];
value[root]=value[right];
value[right]=k;
root=right;
}
else
break;
}
}
}

if the value of the i’th position become update(more less) in the min heap
then update heap ->
value[position] = new min value;
then call UpdateHeap(position);

void UpdateHeap(long root)
{
long up,k;

while(1)
{
if(root==0)
break;
up=(root-1)/2;

if(value[up]>value[root])
{
k=value[root];
value[root]=value[up];
value[up]=k;
root=up;
}
else
break;
}
}

Advertisements