Today we continue exploring effective sorts. Next in line, we have pyramid sort or heap sort. In this article, we`ll examine the classic algorithm of heap sort.
This algorithm uses a data structure called a heap. A heap is a binary tree that meets the rule: each leaf of a tree, that is, a node without descendants, has a depth of d or d-1 where d is the depth of the tree.
Using the example of such a heap, we will analyze the algorithm. The basic principle of this algorithm is based on the construction and modification of the binary tree in such a way that the maximum value is always at its root.
So, let us start. We will follow the algorithm step by step.
Step 1
First, let us figure out how to get a binary tree from a normal unsorted array. Everything is quite simple: starting with the zero element, we sequentially fill the tree levels from left to right, as shown in the figure below. So, the root of the tree is the zero element of the array, its descendants are the first and the second elements, and, accordingly, the descendants of the left branch are the elements 3 and 4, and for the right one are 5 and 6, and so on.
Step 2
Next, we need to transform this tree so that the maximum element is at the root of the tree, and the value in each node is greater than the values in its descendants.
For this purpose, we look at the penultimate level of the tree, and for each node, we check the rule: each descendant must be smaller than its parent. If not, we find the maximum element among the descendants and swap it with the parent. So, we go through each level of the tree, from the bottom up, and as a result, we get a sorting tree that has the maximum number at its root. The converted tree will look like this:
You might wonder where the array is? A good question. The array is the tree. All the permutations we supposedly do in a tree are permutations of elements in the array. The correspondence between array and node indexes was shown in the first figure. In fact, we swapped 1 <-> 4 elements of the array and 2 <-> 6 elements.
The array in this step looks like [9, 8, 4, 7, 3, 1, 2].
Step 3
Now we swap the zero and the last element of the array and "cut" the branch with the maximum element.
The array now looks like this: [2, 8, 4, 7, 3, 1, 9].
Step 4
All that needs to be done next is to similarly shape the tree in accordance with the above-mentioned rule: each descendant must be smaller than its parent. The actions are similar, only now we go from top to bottom and carry out permutations where the rule is violated. In the second iteration, the tree will look like this:
Again, we have the maximum element at the root, and we swap it with the penultimate element of the array since the last element is already the largest among all. We "cut" a branch with the maximum element from the tree. The array will look like this: [1, 7, 4, 2, 3, 8, 9].
Thus, already sorted elements are accumulated at the end of the array. Iterations are performed until the array is fully sorted and all leaves are cut from the tree.
And now the main question is: what was all this for? The pyramid algorithm has excellent computational complexity and does not require additional memory. The proven difficulty estimate is equal to O (n log n) in the worst case, which is incredibly good. This requires only O (1) memory (in fact, a buffer to perform permutations). However, in some implementations, you can do without it.
But there is always a fly in the ointment.
1. This sort is unstable. Keep this in mind if the order of identical elements in the array is important.
2. On almost sorted arrays, this algorithm will run as long as on random arrays. The algorithm is not paralleled and can only be implemented on structures similar to an array where there is direct access to the elements by the index. No such algorithm can be implemented on linked lists.
3. The algorithm will be more efficient on large amounts of data. If the data is small, Shell sort will be more effective.
You should always remember that there is no perfect sorting algorithm, but there is a suitable one. Shortly, we will analyze a few more effective sorting algorithms for you to make your own choice.
