# HEAPSORT ALGORITHM

HEAPSORT(A)

- BUILD_MAX_HEAP(A)
- for i<- length [A] down to 2
- do exchange A[1] <-> A[i]
- heapsize[A]<- heapsize[A] – 1
- MAX_HEAPIFY(A,1)

BUILD_MAX_HEAP(A)

- heapsize[A] <- length [A]
- for i <- length [A]/2 down to 1
- do MAX_HEAPIFY (A,i)

MAX_HEAPIFY(A,i)

- l <- left [i]
- r <- right[i]
- if l <= heapsize [A] & A[l] > A[i]
- then largest <- l
- else largest <- i
- if r <= heapsize[A] and A[r] > A[largest ]
- then largest <- r
- if largest !=i
- then exchange A[i] <-> A[largest]
- MAX_HEAPIFY (A,largest)