Heap Sort
Notes
- Remember a heap is a structure with expected:
- Insertion time of O(log2 n)
- Deletion time of O(log2 n)
- A max-heap keeps the largest value at the top of the heap.
- A heap is implemented as a nearly complete binary tree.
- A heap can be implemented in an array
- parent(i) = return ⌊i/2⌋
- Left(i) = return 2i
- Right(i) = return 2i + 1
-
index 1 2 3 4 5 6 6 Value Root L1 R1 L2 R2 L3 R3 - The Sort
HEAP-SORT (A)
- BUILD-MAX-HEAP(A)
- For i < A.length downto 2
- swap(A[1], A[i])
- heap_size --;
- MAX-HEAPIFY(A, 1)
BUILD-MAX-HEAP(A)
- heap_size ← A.length
- for i ← ⌊ A.length/2 ⌋ down to 1
- MAX-HEAPIFY(A,i)
MAX-HEAPIFY(A,i)
- l ← left(i)
- r ← righ(i)
- pos ← LargestPos(i, l)
- pos ← LargestPos(pos, r)
- If pos ≠ i
- swap(A[i], A[pos])
- MAX-HEAPIFY(A, pos)
LargestPos (a,b)
- rv ← i
- if b < heap_size
- if(A[b] > A[i]
- rv ← b
- return rv
- Try MAX-HEAPIFY with {4, 1, 3, 2, 6, 5, 7}
- Try HEAP-SORT with {4, 1, 3, 2, 6, 5, 7}
- Claim: Max-Heapify is O(log2n)
- A complete binary tree of height h has 2h+1-1 nodes
- From before, a binary tree of height h has 2h leaf nodes.
- So a complete tree will have
- 20 nodes at the root
- 21 nodes at level 1
- 22 nodes at level 2
- ...
- 2h nodes at level h.
- $\Sigma_{i=0}^h2^i = 2^{h+1}-1$
- Think of this as a h bit binary number
- root 000...01
- L1 000...10
- Lh 100...00
- Adding it all up 111...11
- Which is one less that 1000...00, one more bit
- Try it for h = 4
- 1 + 2 + 4 + 8 + 16 = 31 = 25-1
- 000001 + 000010 + 000100 + 001000 + 010000 = 011111
- = 100000-1
- The best split will have 1/2 of the remaining nodes in the subtree.
- T(n) = T(n/2) + c
- Which we have seen is O(logn)
- The worst split will have 2/3n nodes in one sub tree and 1/3n in the other.
- This is a 1/2 complete tree
-
2i nodes / \ 2i-1-1 2i-2-1 - The left sub tree is complete with n/2 nodes in it
- 2i-2 leaf nodes
- 2i-2-1 internal nodes
- The right subtree is complete, but one level shorter, n/4 nodes
- Just divide everything in the previous tree by 2, it is one layer shorter!.
- The total nodes in the subtree is left + right
- total nodes = 2×2i-2(-1) + 2i-2(-1)
- For a total of 3×2i-2
- So it is T(2/3 n) to process the left, and T(1/3n)to process the right.
- So T(n) ≤ T(2/3n) + c in the worst case and T(n/3)+C in the best.
- But we have seen that any fractional split is O(log2n)
- So Max-Heapify is O(log2n)
- It should be clear that BUILD-MAX-HEAP is O(n log2n)
- It should be clear that HEAP-SORT is O(n log2n)
- A complete binary tree of height h has 2h+1-1 nodes