Just to review the selection sort we learned, finding the smallest element in the unordered region requires n-1 comparisons, and finding the second smallest element requires n-2 comparisons until the last one is compared. Heap sorting because of the nature of binary heap, the top of the heap is the largest element, the search times only once, but to turn disorder into ordered middle also requires a pre-processing process: the construction of heap order.
Heap ordering does not mean array ordering, heap ordering satisfies binary heap properties:
1. The parent node’s key always takes precedence over any child node’s key;
2. Both the left and right subtrees are a binary heap.
So heap sorting is divided into two stages, the construction heap ordering and sinking sort stage.
The heap-ordering stage is to reorganize the original data into a binary heap. Heap-ordering means that each node of a binary tree takes precedence over its two child nodes, which does not mean that the array is ordered.
The sinking sort stage is to take out the binary heap with high priority until all elements are taken out, and the array ordered result is obtained.
There are two ways to construct a heap order, one is to float up, the other is to sink. Here’s an example of the maximum heap.
Heap ordering from bottom to top (float up)
Floatation is a comparison between a node and its parent, and if a node is larger than its parent, the heap is repaired by swapping. If the node is still larger than the current parent, you can loop through the repair heap until a larger parent is encountered.
So what node do we start at?
If you float up from the last node in the array, the relationship between the parent node and the grandparent node is uncertain. If the grandparent node is smaller than the parent node, there is no guarantee that the entire binary tree can be binary heaped.
So we start at the left child of the root node, with array subscript 1, and do bottom-up heap ordering. During the loop comparison, the node is already in the repair heap, so you can mark the end of the comparison when the float operation is no longer swapped.
If properly optimized, it is possible to spend less time than the sinking phase.
animation
Algorithm animation video address
Code
Result
Initial state [13, 9, 15, 11, 3, 7, 17, 5, 1]
Exchange [15, 9, 13, 11, 3, 7, 17, 5, 1]
Exchange [15, 11, 13, 9, 3, 7, 17, 5, 1]
Exchange [15, 11, 17, 9, 3, 7, 13, 5, 1]
Exchange [17, 11, 15, 9, 3, 7, 13, 5, 1]
[17, 11, 15, 9, 3, 7, 13, 5, 1]
Top-down heap ordering (sinking)
Sink is the comparison between the current node and the left and right children, and it starts at the non-leaf node, the parent of the last node in the array, in the process of ordering the heap from top to bottom.
animation
Algorithm animation video address
Code
Result
Initial state [13, 9, 15, 11, 3, 7, 17, 5, 1]
Exchange [13, 9, 17, 11, 3, 7, 15, 5, 1]
Exchange [13, 11, 17, 9, 3, 7, 15, 5, 1]
Exchange [17, 11, 13, 9, 3, 7, 15, 5, 1]
Exchange [17, 11, 15, 9, 3, 7, 13, 5, 1]
[17, 11, 15, 9, 3, 7, 13, 5, 1]
Sinking sorting
The main work of heap sorting is done in the second stage, sink sorting. Here we take the largest element in the heap and swap it with the last element in the array, and the array’s operable length shrinks by one position. It then sinks from the top of the heap, no matter how many times, until the array’s operable length is 1.
animation
Algorithm animation video address
Code
Result
Initial state [13, 9, 15, 11, 3, 7, 17, 5, 1]
Orderly heap
Exchange [13, 9, 17, 11, 3, 7, 15, 5, 1]
Exchange [13, 11, 17, 9, 3, 7, 15, 5, 1]
Exchange [17, 11, 13, 9, 3, 7, 15, 5, 1]
Exchange [17, 11, 15, 9, 3, 7, 13, 5, 1]
The sorting
Exchange [15, 11, 1, 9, 3, 7, 13, 5, 17]
Exchange [15, 11, 13, 9, 3, 7, 1, 5, 17]
Exchange [13, 11, 5, 9, 3, 7, 1, 15, 17]
Exchange [13, 11, 7, 9, 3, 5, 1, 15, 17]
Exchange [11, 1, 7, 9, 3, 5, 13, 15, 17]
Exchange [11, 9, 7, 1, 3, 5, 13, 15, 17]
Exchange [9, 5, 7, 1, 3, 11, 13, 15, 17]
Exchange [7, 5, 3, 1, 9, 11, 13, 15, 17]
Exchange [5, 1, 3, 7, 9, 11, 13, 15, 17]
[1, 3, 5, 7, 9, 11, 13, 15, 17]
Like this article friends, wechat search “algorithm clear strategy” public number, watch more wonderful algorithm animation articles