[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 05:17:21 AEDT
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.

Sorting, Heaps:   Introduction

Priority Queue

NB. not an ordinary [Queue]! - revision.

Priority Queue Operations:

Heap

Array as Heap

Heap

(1. It is possible, but less convenient, to use a[0..n-1].)
(2. Can have a similar definition for small elements on top.)

Heap

Heap Sort

Yet another sorting idea

Sounds like a mirror image of selection sort.   But much faster with a heap / priority queue!
©
L
.
A
l
l
i
s
o
n

Heap Sort

Heap Sort

[also study this at home!]
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*/

Properties of Heap Sort

Sorting, Heaps:   Summary

Prepare

© L.Allison, Sunday, 28-Nov-2021 05:17:21 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/05heap.shtml
Computer Science, Software Engineering, Science (Computer Science).