[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Wednesday, 08-May-2024 12:59:35 AEST Instructions:
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
downHeap(int a[], int k, int N)
/* PRE: a[k+1..N] is a heap */
/* POST: a[k..N] is a heap */
{ int newElt, child;
newElt=a[k];
while(k <= N/2) /* k has child(s) */
{ child = 2*k;
if(child < N && a[child] < a[child+1]) /* pick larger */
child++; /* child */
if(newElt >= a[child]) break;
/* else */
a[k] = a[child]; /* move child up */
k = child;
}
a[k] = newElt;
}/*downHeap*/
[also study this at home!]
heapSort(int a[], int N)
/* sort a[1..N], N.B. 1 to N */
{ int i, temp;
for(i=N/2; i >= 1; i--)
downHeap(a, i, N);
/* a[1..N] is now a heap */
for(i=N; i > 1; i--)
{ temp = a[i];
a[i]=a[1]; /* largest of a[1..i] */
a[1]=temp;
downHeap(a,1,i-1); /* restore a[1..i-1] heap */
}
}/*heapSort*/