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
Master’s 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
Master’s 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 + 1
A [ A.heapsize] = -∞ Increase-key(A, A.heapsize, key)
Priority queues
Runtime?
Maximum = Extract-Max = Increase-Key = Insert =
Priority queues
Runtime?
Maximum = O(1) Extract-Max = O(lg n) Increase-Key = O(lg n) Insert = O(lg n)
Priority queues
Name 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=kPRA0W1kECg
Sorting comparisons: