Heapsort is another very

efficient sorting

algorithm. The

time it runs is O(nlgn), and you cant get better than that.

The

data structure used in this

sorting algorithm is the

Heap. A

Binary Tree in which every

parent is bigger or equal to his children.

Heaps can be implemented in many different ways, using

arrays or

Dynamic Structures.

**The sub-routines neccessary to maintain a heap**:

*Note:* The following procedures assume that the heap is stored inside an

Array.

Parent(I)

Left(I)

Right(I)

These three fundamental

procedures will return the parent, the left child or the right child of the I node. They can return the number of the

cell in the array in which the value is stored, or a

pointer for that node. Depends on how you are implementing the heap.

Heapify(A,I)

// A is either the array that stores the heap and I is the index of the node.

// This

recursive procedure assumes that the sub-trees of I are heaps, but A(i) could be smaller than one of the nodes in these sub-trees and fixes the problem.

// The running time of Heapify is O(nlgn)

l<--Left(I)

r<--Right(I)

**if** l<=Heapsize(A) and A(l)>A(i)

**then**
largest<--l

**else**
lasgest<--i

**if** r<=Heapsize(A) and A(r)>A(largest)

**then**
largest<--r

**if** largest <> i

**then**
A(i)<-->A(largest)

Heapify(A,largest)

Build_Heap(A)

//Takes a regular array and makes a heap out of it by heapifying all the non-

leaf nodes.

// The running time of Buildheap is O(nlgn)

Heapsize(A)<--Length(A)

**for** i<--Parent(A(Heapsize(A))

**downto** 1

**do** Heapify(A,i)

And finally, the Heapsort algorithm. First, the

Algorithm turns the array to a heap, and then, since the first node is the biggest it replaces it with the last node and decreases the heap size by one. Now the biggest number is in the correct spot, and the process repeats.

Heapsort(A)

// The running time of Heapsort is O(nlgn)

Build_Heap(A)

**for** i<--length(A)

**downto** 2

**do** A(1)<-->A(i)

Heapsize(A)<--Heapsize(A)-1

Heapify(A,1)

*Note: These algorithms can be easily changed if you prefer to implement heaps using dynamic structures.*