[SOLVED] CS Heapsort

Heapsort

Use a stable sort to sort from the least significant digit to most
Pseudo code: (A=input) for i = 1 to d
stable sort of A on digit i // i.e. use counting sort
4
Radix sort

Stable means you can draw lines without crossing for a single digit
5
Radix sort

Run time?
6
Radix sort

Run time?
O( (b/r) (n+2r) )
b-bits total, r bits per digit
d = b/r digits
Each count sort takes O(n + 2r) runs count sort d times
O( d(n+2r)) = O( b/r (n + 2r))
7
Radix sort

Run time?
if b < lg(n), (n)if b > lg(n), (n lg n)
8
Radix sort

Heapsort

It is possible to represent binary trees as an array
1|2|3|4|5|6|7|8|9|10
Binary tree as array

index i is the parent of 2i and 2i+1
1|2|3|4|5|6|7|8|9|10
Binary tree as array

Is it possible to represent any tree with a constant branching factor as an array?
Binary tree as array

Is it possible to represent any tree with a constant branching factor as an array?
Yes, but the notation is awkward
Binary tree as array

A max heap is a tree where the parent is larger than its children (A min heap is the opposite)
Heaps

The idea behind heapsort is to:
1. Build a heap
2. Pull out the largest (root) and re-compile the heap
3. (repeat)
Heapsort

To do this, we will define subroutines:
1. Max-Heapify = maintains heap property
2. Build-Max-Heap = make sequence into a max-heap
Heapsort

Input: a root of two max-heaps Output: a max-heap
Max-Heapify

Pseudo-code Max-Heapify(A,i):
left = left(i) // 2*i
right = right(i) // 2*i+1
L = arg_max( A[left], A[right], A[ i ]) if (L not i)
exchange A[ i ] with A[ L ]
Max-Heapify(A, L) // now make me do it!
Max-Heapify

Runtime?
Max-Heapify

Runtime?
Obviously (is it?): lg n
T(n) = T(2/3 n) + O(1) // why? Or
T(n) = T(1/2 n) + O(1)
Max-Heapify

Masters theorem: (proof 4.6)
For a > 1, b > 1,T(n) = a T(n/b) + f(n)
If f(n) is (3 cases)
O(nc) for c < log a, T(n) is (nlogb a) b(nlogb a), then T(n) is (nlogb a lg n)(nc) for c > log a, T(n) is (f(n)) b
Masters theorem

Runtime?
Obviously (is it?): lg n
T(n) = T(2/3 n) + O(1) // why? Or
T(n) = T(1/2 n) + O(1) = O(lg n)
Max-Heapify

Next we build a full heap from an unsorted sequence
Build-Max-Heap(A)
for i = floor( A.length/2 ) to 1
Max-Heapify(A, i)
Build-Max-Heap

Red part is already Heapified
Build-Max-Heap

Correctness: show i to n a heap Base: Each alone leaf is a
max-heap
Step: if A[i] to A[n] are in a heap,
then Heapify(A, i-1) will make
i-1 a heap as well Termination: loop ends at i=1,
which is the root (so all heap)
Build-Max-Heap

Runtime?
Build-Max-Heap

Runtime?
O(n lg n) is obvious, but we can get a better bound
Show ceiling(n/2h+1) nodes at any level h, with h=0 as bottom
Build-Max-Heap

Heapify from height h takes O(h)
Build-Max-Heap

Heapsort(A): Build-Max-Heap(A) for i = A.length to 2
Swap A[ 1 ], A[ i ] A.heapsize = A.heapsize 1 Max-Heapify(A, 1)
Heapsort

Runtime?
Heapsort

Runtime?
Run Max-Heapify O(n) times So O(n lg n)
Heapsort

Heapsort

You try it!
Sort: A = [1, 6, 8, 4, 7, 3, 4]
Heapsort

First, build the heap starting here
A = [1, 6, 8, 4, 7, 3, 4]
A = [1, 6, 8, 4, 7, 3, 4]
A = [1, 7, 8, 4, 6, 3, 4]
A = [8, 7, 1, 4, 6, 3, 4] recursiv A = [8, 7, 4, 4, 6, 3, 1] done
Heapsort
e

Move first to end, then re-heapify A = [8, 7, 4, 4, 6, 3, 1], move end A = [1, 7, 4, 4, 6, 3, 8], heapify
A = [7, 1, 4, 4, 6, 3, 8], rec. heap A = [7, 6, 4, 4, 1, 3, 8], move end A = [3, 6, 4, 4, 1, 7, 8], heapify
A = [6, 3, 4, 4, 1, 7, 8], rec. heap A = [6, 4, 4, 3, 1, 7, 8], next slide..
Heapsort

A = [6, 4, 4, 3, 1, 7, 8], move end A = [1, 4, 4, 3, 6, 7, 8], heapify
A = [4, 4, 1, 3, 6, 7, 8], move end A = [3, 4, 1, 4, 6, 7, 8], heapify
A = [4, 3, 1, 4, 6, 7, 8], move end A = [1, 3, 4, 4, 6, 7, 8], heapify
A = [3, 1, 4, 4, 6, 7, 8], move end A = [1, 3, 4, 4, 6, 7, 8], done
Heapsort

Heaps can also be used to implement priority queues (i.e. airplane boarding lines)
Operations supported are: Insert, Maximum, Extract-Max and Increase-key
Priority queues

Maximum(A): return A[ 1 ]
Extract-Max(A):
max = A[1]
A[1] = A.heapsize
A.heapsize = A.heapsize 1 Max-Heapify(A, 1), return max
Priority queues

Increase-key(A, i, key):
A[ i ] = key
while ( i>1 and A [floor(i/2)] < A[i]swap A[ i ], A [floor(i/2)] i = floor(i/2)Opposite of Max-Heapify… move high keys up instead of low down Priority queues)Insert(A, key):A.heapsize = A.heapsize + 1A [ A.heapsize] = – Increase-key(A, A.heapsize, key) Priority queuesRuntime?Maximum = Extract-Max = Increase-Key = Insert = Priority queuesRuntime?Maximum = O(1) Extract-Max = O(lg n) Increase-Key = O(lg n) Insert = O(lg n) Priority queuesName Average Worst-case Insertion[s,i] Merge[s,p] Heap[i] Quick[p] Counting[s] Radix[s] Bucket[s,p]O(n2)O(n lg n) O(n lg n) O(n lg n) O(n + k) O(d(n+k)) O(n)O(n2)O(n lg n)O(n lg n) O(n2)O(n + k)O(d(n+k)) O(n2)Sorting comparisons: https://www.youtube.com/watch?v=kPRA0W1kECgSorting comparisons: