The

**Heapify(A, i){**
**
l <- left(i)**
**
r <- right(i)**
**
if l <= heapsize[A] and 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 swap A[i] <-> A[largest]**
**
Heapify(A, largest)**
** }**

** Buildheap(A){**
**
heapsize[A] <- length[A]**
**
for i <- |length[A]/2| downto 1**
**
do Heapify(A, i)**
** }**

** Heapsort(A){**
**
Buildheap(A)**
**
for i <- length[A] downto 2**
**
do swap A[1] <-> A[i]**
**
heapsize[A] <- heapsize[A] - 1**
**
Heapify(A, 1)**
** }**

Heap Sort operates by first converting the initial array into a heap. The HeapSort algorithm uses a process called Heapify to accomplish its job. The Heapify algorithm, as shown above, receives a binary tree as input and converts it to a heap. The root is then compared with its two immediate children, and the larger child is swapped with it. This may result in one of the left or right subtrees losing their heap property. Consequently, the Heapify algorithm is recursively applied to the appropriate subtree rooted at the the node whose value was just swapped with the root and the process continues until either a leaf node is reached, or it is determined that the heap property is satisfied in the subtree.

The entire HeapSort method consists of two major steps:

STEP 1: Construct the initial
heap using adjust (N/2) times on all non-leaf nodes.

STEP 2: Sort by swapping and
adjusting the heap (N-1) times.

In step 2, since the largest element of the heap is always at the root, after the initial heap is constructed, the root value is swapped with the lowest, rightmost element. This node corresponds to the last element of the array and so after the swapping the righmost element of the array has the largest value, which is what we want it to have. Consequently, the rightmost element is correctly place, and so the corresponding node becomes a light gray in the tree display depicting the heap. Also, the elements (nodes) chosen for swapping at this point of the algorithm are shown as yellow nodes.

Thereafter, since the value
of the lowest, rightmost node has moved up to the root, the heap property
of the rest of the heap (minus the gray nodes) has been disturbed. Consequently,
now the Heapify process is applied to the rest of the heap (treating the
light gray nodes as though they were no longer a part of the heap). Once
the rest of the heap is again converted to a proper heap, the swapping
process as described in the previous paragraph, followed by the Heapify
process is applied again. This continues until the root node of the heap
turns light gray - i.e., the root has its correct value. Then, the array
is sorted.

At each step of the Heapify algorithm, a node is compared to its children and one of them is chosen as the next root. One level of the tree is dropped at each step of this process. Since the heap is a complete binary tree, there are atmost log(N) levels. Thus, the worst case time complexity of Heapify is O(log(N)). In the Heapsort algorithm, Heapify is used (N/2) times to construct the initial heap and (N-1) times to sort. Thus the Heapsort algorithm has a worst case time complexity of O(N*log(N)).