HeapSort Review

This is a review about HeapSort by CLRS#3 & Algorithm#4.

Complexity

• Average
  $$
  T(n) = \Theta(n\lg{n})
  $$

<CLRS#3>

MAX_HEAPIFY

MAX_HEAPIFY(A,i):
	l = LEFT(A,i)
	r = RIGHT(A,i)
	if l <= A.heap-size && A[l] > A[i]
		largest = l
	else largest = i
	if r <= A.heap-size && A[l] > A[largest]
		largest = r
	if largest != i
		exchange A[i] with A[largest]
		MAX_HEAPIFY(A,largest)

BuildMaxHeap

BuildMaxHeap(A):
	A.heap-size = A.length
	for i = A.length/2 to 1
		MAX_HEAPIFY(A,i)

<Algorithm#4>

HeapSort

swim(A,k):
	if k > 1
    if A[k] > A[k/2]
      exchange A[k] with A[k/2]
      swim(A,k/2)

sink(A,k):
	if k < A.length/2
		if A[k] < A[k*2]
      	exchange A[k] with A[k*2]
      	sink(a,k*2)

BuildMaxHeap(A):
	for i = A.length/2 to 1
		sink(A,i)