Heap Sort
The (binary) heap data structure is an array object that we can view as a
nearly complete binary tree.
although A[1 .. A: length] may contain numbers, only the elements in A[1..A:heap-size], where 0 <= A:heap-size <= A:length, are valid elements of the heap. PARENT(i)
1 return [i/2]
LEFT(i)
1 return 2*i
RIGHT(i)
1 return 2*i + 1 | |
max-heap: A[PARENT(i)] >= A[i]
height is Θ(lg n)
MAX-HEAPIFY(A,i) //heapify a specific node (move it down tree if necessary)
1 l = LEFT(i)
2 r = RIGHT(i)
3 if l <= heap-size[A] and A[l] > A[i]
4 then largest = l
5 else largest = i
6 if r <= heap-size[A] and A[r] > A[largest]
7 then largest = r
8 if largest != i
9 then exchange A[i] <-> A[largest]
10 MAX-HEAPIFY(A,largest)
The size of a subtree is at most 2n/3, which occurs when the last row is exactly half full. So the worst case running time T(n) satisfies the recurrence: T(n) <= T(2n/3) + Θ(1) Which by case 2 of the "Master Theorem" has the solution: T(n) = O(lg n). because a = 1 then nlogba becomes O(1), therefore ti is equal to f(n), hence O(1* lg n) BUILD-MAX-HEAP(A)
1 A.heap-size = A.length
2 for i = floor(A.length/2) downto 1 //the entries in A[floor(n/2)+1..n] are all leaves
3 MAX-HEAPIFY(A,i)
Heap-Sort: Build maxheap O(lg n) + traverse (n lg n) => O(n lg n)
|
|
