Heapsort

Animation showing the operation of heapsort.

The system by mounds (heapsort in English) is a non-recurrent, unstable, computational system algorithm Strike Strike (nlog n){displaystyle Theta (nlog n)}.

This algorithm consists of storing all the elements of the vector to be ordered in a heap (heap), and then extracting the node that remains as the root node of the heap (top) in successive iterations obtaining the set tidy. It bases its operation on a heap property, whereby the top always contains the smallest element (or the largest, depending on how the heap has been defined) of all those stored in it. The algorithm, after each extraction, repositions the last leaf on the right of the last level at the root or top node. Which destroys the heap property of the tree. But, then it performs a process of "descent" of the inserted number in such a way that the greater of its two children is chosen at each movement, with which it is exchanged. This exchange, carried out successively "sinks" the node in the tree restoring the heap property of the tree and making way for the next extraction of the root node.

The algorithm, in its usual implementation, has two phases. First a phase of building a heap from the set of input elements, and then a phase of successive extraction of the top of the heap. The implementation of the data store in the heap, despite being conceptually a tree, can be easily done in a vector. Each node has two children and therefore, a node located at position i of the vector will have its children at positions 2 x i, and 2 x i +1 assuming that the first element of the vector has index = 1. That is, the top occupies the initial position of the vector and its two children the second and third position, and so on. Therefore, in the ordering phase, the exchange occurs between the first element of the vector (the root or top of the tree, which is the largest element of the tree) and the last element of the vector, which is the rightmost leaf in the tree. last level. The tree loses a leaf and therefore reduces its size by one element. The definitive and ordered vector begins to be built at the end and ends at the beginning.

Description

Here is a pseudocode description of the algorithm. Descriptions of the operations insert_into_heap and remove_top_of_heap can be found in the article on heaps.

function heapsort(array A[0.n]):
 mound M
 integer i; // variable declaring i
 for i = 0.
 insert_en_monticulo(M, A[i])
 for i = 0.
A[i] = extract_cima_from_monticulo(M)
 return A