Two new function needed to rearrange the heap proper way again.The two functions are Downheap and Upheap.

void Downheap( int heap[], int start, int finish)
{
/* here heap is a linear array, start is the index of the element from where downheap operation is to start, and finish is the index of the last (bottom) element of the heap. */

int index, lchild, rchild, maximum, temp;
lchild=2*start; /* index of left child */
rchild=lchild +1; /* index of right child */

if( lchild <= finish)
{
maximum= heap[lchild];
index= lchild;
if ( rchild <= finish )
{
if( heap[rchild] > maximum)
{
maximum = heap[rchild];
index = rchild;
}
}
if( heap[start] < heap [index])
{
temp = heap[start];
heap[start] = heap [index];
heap[index] = temp;
Downheap ( heap, index, finish);
}
}
}

void Upheap( int heap[], int start)
{
/* Here heap is a linear array, start is the index of the element from where upheap operation is to start. */

int temp, parent;
if (start >1)
{
parent = start / 2;
if ( heap[parent] < heap[start] )
{
temp = heap[start];
heap[start] = heap [ parent];
heap[parent] = temp;
Upheap(heap,parent);
}
}
}

/* function for insertion of a node in heap */

void InsertElement( int heap[],int * n, int item )
{
(*n) ++;
heap[*n-1]=item;
Upheap(heap, *n-1);
}

/* function for deleting of a node in a heap */

int DeleteElement( int heap[], int *n)
{
int temp;
temp = heap[1];
heap[1] = heap[*n]
(*n)--;
Downheap( h, 1, *n);
return temp;
}

--------------------------------------------------------
Human do error, please email:- webmaster@piyadas-world.com if you find any. Please visit http://www.piyadas-world.com for more resource.

0 comments