Heap sorting is divided into two processes:
1. Build a pile.
The heap is essentially a completely binary tree and must meet the following: the keywords of any non-leaf node in the tree are not greater than (or not less than) the keywords of the child (if there is) the node.
The heap is divided into: a large root heap and a small root heap. Ascending order is used to sort large root heap, and descending order is used to sort small root heap.
If it is a large root heap, the node with the largest value is adjusted to the heap root by adjusting the function.
2. Save the heap root at the tail and call the adjustment function for the remaining sequence. After the adjustment is completed, save the maximum follower at the tail -1 (-1, -2, ..., -i), and then adjust the remaining sequence. Repeat the process until the sorting is completed.
The code copy is as follows:
//Adjust the function
function headAdjust(elements, pos, len){
//Save the current node value
var swap = elements[pos];
//Locate the child node to the left of the current node
var child = pos * 2 + 1;
//Recursive until there are no children
while(child < len){
//If the current node has a child node on the right and the right child node is larger, use the right child node
//Compare with the current node
if(child + 1 < len && elements[child] < elements[child + 1]){
child += 1;
}
//Compare the current node with the largest child node, if the value is less than, perform value exchange, and locate the current node after the exchange
//On the child node
if(elements[pos] < elements[child]){
elements[pos] = elements[child];
pos = child;
child = pos * 2 + 1;
}
else{
break;
}
elements[pos] = swap;
}
}
//Build the heap
function buildHeap(elements){
// Start from the last node with the child node, compare the node with its child node,
// After exchanging the largest number with this node, the same exchange process is performed to the front node in turn.
// Until a large top heap is built (ascending order is large top, descending order is small top)
for(var i=elements.length/2; i>=0; i--){
headAdjust(elements, i, elements.length);
}
}
function sort(elements){
//Build the heap
buildHeap(elements);
//Adjust from the end of the sequence
for(var i=elements.length-1; i>0; i--){
//The top of the pile is always the largest element, so the top of the pile and the tail element will be exchanged.
//The maximum element is saved at the end and does not participate in subsequent adjustments
var swap = elements[i];
elements[i] = elements[0];
elements[0] = swap;
//Make adjustments, adjust the maximum element to the top of the heap
headAdjust(elements, 0, i);
}
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log(' after: ' + elements);
efficiency:
Time complexity: best: O(nlog2n), worst: O(nlog2n), average: O(nlog2n).
Space complexity: O(1).
Stability: Unstable