Heapsort is another very efficient
. 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
The following procedures assume that the heap is stored inside an Array
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.
// 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<=Heapsize(A) and A(l)>A(i) then
r<=Heapsize(A) and A(r)>A(largest) then
largest <> i then
//Takes a regular array and makes a heap out of it by heapifying all the non-leaf
// The running time of Buildheap is O(nlgn)
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.
// The running time of Heapsort is O(nlgn)
Note: These algorithms can be easily changed if you prefer to implement heaps using dynamic structures.