1. I have to talk about binary trees
To understand the heap, you must first understand the binary tree. In computer science, a binary tree is a tree structure with at most two subtrees per node. Usually subtrees are called "left subtree" and "right subtree". Binary trees are often used to implement binary search trees and binary heaps.
Each node of a binary tree has at most two subtrees (nodes with degrees greater than 2). The subtrees of a binary tree can be divided into left and right, and the order cannot be reversed. The i-th layer of the binary tree has at most 2i - 1 node; the binary tree with a depth of k has at most 2k - 1 node; for any binary tree T, if the number of terminal nodes is n0 and the number of nodes with a degree of 2 is n2, n0 = n2 + 1.
There are three main differences between a tree and a binary tree:
The number of nodes in the tree is at least 1, while the number of nodes in the binary tree can be 0.
There is no limit on the maximum degree of nodes in the tree, while the maximum degree of nodes in the binary tree is 2
There is no difference between left and right in the nodes of a tree, while there is no difference between left and right in the nodes of a binary tree.
Binary trees are divided into complete binary trees and full binary trees.
Full binary tree: A tree with a depth of k and has 2k - 1 node is called a full binary tree
(full binary tree with depth 3)
Complete binary tree: A binary tree with n nodes with depth k. It is called a complete binary tree if and only if each of its nodes corresponds to a node with sequence numbers of 1 to n in a full binary tree with depth k.
(Full binary tree with depth 3)
2. What is a heap?
A heap (binary heap) can be regarded as a complete binary tree. An "excellent" property of a complete binary tree is that, except for the bottom layer, each layer is full, which allows the heap to be represented by an array (ordinary general binary trees are usually represented by linked lists as basic containers), and each node corresponds to an element in the array.
The following figure shows the relationship between a heap and an array
(The relationship between heap and array)
For the given subscript i of a node, it can be easily calculated for the subscript of the parent node and child node of this node:
Parent(i) = floor(i/2), the parent node subscript of i
Left(i) = 2i, the left child node subscript of i
Right(i) = 2i + 1, the right child node subscript of i
There are generally two types of binary heaps: the largest heap and the smallest heap.
Maximum heap:
The maximum element value in the maximum heap appears at the root node (top of the heap)
The element value of each parent node in the heap is greater than or equal to its child node (if it exists)
(Maximum heap)
Minimum heap:
The minimum element value in the minimum heap appears at the root node (top of the heap)
The element value of each parent node in the heap is less than or equal to its child node (if it exists)
(Minimum stack)
3. Principle of heap sorting
Heap sorting is to take out the maximum number at the top of the maximum heap, continue to adjust the remaining heap to the maximum heap, and take out the maximum number at the top of the heap again. This process continues until there is only one remaining number. Define the following operations in the heap:
Max-Heapify: Adjust the end node of the heap so that the child node is always smaller than the parent node
Create a maximum heap (Build-Max-Heap): Reorder all data of the heap to make it the maximum heap
Heap-Sort: Remove the root node of the first data and perform recursive operation of maximum heap adjustment
Before continuing the following discussion, one issue that needs to be noted is: the arrays are all Zero-Based, which means that our heap data structure model will change.
(Zero-Based)
Correspondingly, several calculation formulas must also be adjusted accordingly:
Parent(i) = floor((i-1)/2), the parent node subscript of i
Left(i) = 2i + 1, the left child node subscript of i
Right(i) = 2(i + 1), the right child node subscript of i
The function of Max Heap Adjustment (MAXHEAPIFY) is to maintain the properties of the largest heap and is the core subroutine for creating the largest heap. The operation process is shown in the figure:
(Max-Heapify)
Since the heap still violates the heap nature after one adjustment, recursive testing is required so that the entire heap satisfies the heap nature. It can be expressed in JavaScript as follows:
/** * Check from index and maintain maximum heap properties* * @array * * The starting index of the @index check* * @heapSize Heap size* **/function maxHeapify(array, index, heapSize) { var iMax = index, iLeft = 2 * index + 1, iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); maxHeapify(array, iMax, heapSize); // Recursive adjustment}}function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp;}Generally speaking, recursion is mainly used in the method of division and treatment, and there is no need for division and treatment here. Moreover, recursive calls require stack pressing/clearing, which has a slight disadvantage in performance compared to iteration. Of course, this can be ignored according to the 20/80 rule. But if you think using recursion will make you feel uncomfortable, you can also use iteration, such as the following:
/** * Check from index and maintain maximum heap properties* * @array * * The starting index of the @index check* * @heapSize Heap size* **/function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } }}function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp;}The purpose of creating a maximum heap (Build-Max-Heap) is to transform an array into a maximum heap, accepting two parameters of array and heap size. Build-Max-Heap will call Max-Heapify from the bottom up to transform the array and build the maximum heap. Because Max-Heapify can ensure that the nodes after subscripting i meet the properties of the largest heap, bottom-up call to Max-Heapify can maintain this property during the transformation process. If the maximum heap number element is n, then Build-Max-Heap calls Max-Heapify in sequence from Parent(n). The process is as follows:
The description is as follows in JavaScript:
function buildMaxHeap(array, heapSize) { var i, iParent = Math.floor((heapSize - 1) / 2); for (i = iParent; i >= 0; i--) { maxHeapify(array, i, heapSize); }}Heap-Sort is the interface algorithm for heap sorting. Heap-Sort first calls Build-Max-Heap to transform the array into the maximum heap, then exchanges the top and bottom elements of the heap, then rises the bottom, and finally calls Max-Heapify to maintain the maximum heap properties. Since the top element of the heap must be the largest element in the heap, after one operation, the largest element present in the heap is separated from the heap from the heap, and after repeated n-1 times, the array is arranged. The entire process is as follows:
The description is as follows in JavaScript:
function heapSort(array, heapSize) { buildMaxHeap(array, heapSize); for (int i = heapSize - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } }4. JavaScript language implementation
Finally, organize the above into complete javascript code as follows:
function heapSort(array) { function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function buildMaxHeap(array) { var i, iParent = Math.floor(array.length / 2) - 1; for (i = iParent; i >= 0; i--) { maxHeapify(array, i, array.length); } } function sort(array) { buildMaxHeap(array); for (var i = array.length - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } return array; } return sort(array);}5. Application of heap sorting algorithm
(1) Algorithm performance/complexity
The time complexity of heap sort is very stable (we can see that it is not sensitive to input data), and is O(nn) complexity, the best case is the same as the worst case.
However, its spatial complexity varies according to implementation. The above discusses two common complexities: O(n) and O(1). Based on the principle of saving space, I recommend the O(1) complexity method.
(2) Algorithm stability
There are a large number of filtering and moving processes in heap sorting, which belongs to an unstable sorting algorithm.
(3) Algorithm applicable scenario
Heap sorting will incur relatively large overhead in the process of building the heap and adjusting the heap, and it is not applicable when there are few elements. However, when there are many elements, it is still a good choice. Especially when solving problems such as "the number of top n large", it is almost the preferred algorithm.