Entrepreneurials‎ > ‎Jobs‎ > ‎Interview‎ > ‎Examples‎ > ‎

Sort




Heap Sort

Heap

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)














Comments