HEAP SORT

 

 

The heapsort algorithm starts by using BUILD-HEAP to build a heap on the input array A[1 . . n], where n = length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If node n is now "discarded" from the heap (by decrementing heap-size[A]), it is evident that A[1 . . (n - 1)] can be easily made into a heap. The children of the root remain heaps, but the new root element may violate the heap property. In order to restore the heap property, one call to HEAPIFY(A, 1) leaves a heap in A[1 . . (n - 1)]. The heapsort algorithm then repeats this process for the heap of size n - 1 down to a heap of size 2.

 

HEAPSORT(A)

1 BUILD-HEAP(A)

2 for i -> length[A] downto 2

3 do exchange A[1] <-> A[i]

4 heap-size[A] <- heap-size[A] -1

5 HEAPIFY(A, 1)

 

The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-HEAP takes time O(n) and each of the n - 1 calls to HEAPIFY takes time O(lg n).

 

BUILD-HEAP(A)

1 heap-size[A] <- length[A]

2 for i <- length[A]/2 downto 1

3 do HEAPIFY(A, i)


HEAPIFY(A, i)

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 HEAPIFY(A,largest)

 

 

The heap sort algorithm:
  1. Start by constructing a heap.

  2. Once the heap is constructed, the element in the first position of the array will be the maximum and can be swapped into its correct position. That swap disrupts the heap, but it can be rebuilt by looking at a small portion of the elements in the array using the "heapify" procedure .