[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

• Have seen the simple O(n2)-time sorting algorithms

• proved them, analysed them, etc..

• Now, the fastest (general) sorting algorithms take O( n . log(n) )-time

• e.g. Heap sort

• relies on the heap data-structure

• which also implements a priority queue . . .

## Priority Queue

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

Priority Queue Operations:

• create an empty priority queue

• add a given element with a given priority

• remove the element with the highest (lowest) priority

Heap

Array as Heap

## Heap

• The children of a[ i ] are

• left:   a[ 2 * i ] and
• right: a[ 2 * i + 1 ] (if they exist)

• a[ i .. j ] is a heap iff

1. i >= 1 and
2. every element, a[ k ], i<=k<=j, is at least as large as its children, if any

• So . . . if a[ 1 .. n ] is a heap, then a[ 1 ] must be the largest element
(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

• [use demo]

• [note assertions, proof etc.]

• [draw diagrams of up- and down-heap]

## Heap Sort

Yet another sorting idea

• Find biggest element

• put it at a[n]

• find next biggest

• put it at a[n-1], ...

• etc. . . .
Sounds like a mirror image of selection sort.   But much faster with a heap / priority queue!

Heap Sort

• Make a[1..n] into a heap

• so biggest element is at a[1]

• move a[1] to a[n]

• by swapping a[1] and a[n], but . . .

• may destroy heap property, so . . .

• . . . use downHeap on a[ 1 .. n-1 ] to restore

• then 2nd largest value at a[1]

• etc. . . .

Heap Sort

• examine code (below)

• [use demo]

• [note assertions, proof]

• [do examples]
[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

• Complexity

• Time

• O(n . log(n)), best, average and worst cases,   because [_________________]

• slower than Quick sort on-average, but better worst-case

• Space

• O( 1 )-space   because [____________]

• not stable,   because [______________]

## Sorting, Heaps:   Summary

• priority queue, insert & delete_top, O(log(n))-time.

• uses include heap sort and Kruskal's algorithm

• compare and contrast with "ordinary" Queue

• Heap sort

• always fast, O(n . log(n))-time

• good space complexity, O(1)

## 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).