Page 249 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes void adjust(int x[], int i, int n)

{
int j, k;
int flag;
k = x[i];
flag = 1;
j = 2 * i;
while(j <= n && flag == 1)
{
if((j < n) && (x[j] < x[j+ 1]))
j++;
if(k >= x[j])
flag = 0;
else
{
x[j / 2] = x[j];
j = j * 2;
}
}
x[j / 2] = k;
}
void build_initial_heap(int x[], int n)
{
int i;
for(i = n / 2; i >= 1; i--)
adjust(x, i, n);
}
void heapsort(int x[], int n)
{
int i;
build_initial_heap(x, n);
for(i = n-l; i >= 1; i--)
{
exchange(x[1], x[i+ 1]);
adjust(x,l,i);
}
Analysis of Heapsort

In each pass of while loop in procedure adjust( x,i,n), the position i is doubled, hence the number
of passes cannot exceed (loge n div i). Therefore the computation time of adjust is O(log n div

244 LOVELY PROFESSIONAL UNIVERSITY