Heap sorting

Heapsort 1. Consider array x as a complete binary tree and use the Heapify algorithm to convert thi t t hthis tree to a heap. 2. For i = n-1 down to 1:

h [ ] d [ ] h ha. Interchange x[0] and x[i], thus putting the largest element in the sublist x[0],...,x[i] at end of sublist.sublist. b. Apply the TrickleDown algorithm to convert the binary tree corresponding to the sublist stored in

iti 0 th h i 1 f

50

positions 0 through i - 1 of x.

Example for HeapSort 16 14

14 10 8 10

8 7 9 3 4 7 9 3

4 1 2 1 16 i

51

i

Example for HeapSort 10 9

8 9 8 3

4 7 1 3 4 7 1 2

14 16 i

10 14 16 i

52

i i

Example for HeapSort 8

7 3

7

4 37 3 4 3

4 2 1 9 i

1 2 8 9 i

14 16 10 14 16

53

Example for HeapSort 4

2 3

3

2 12 3 2 1

1 7 8 9 i

4 7 8 9 i

14 16 10 14 16

54

Example for HeapSort 2

1 3

1

2 31 3

4 7 8 9

i 2 3

4 7 8 9

i

4 7 8 9 4 7 8 9

14 16 10 14 16

55

1 2 3 4 7 8 9 10 14 16