JS implements heap sorting

This article mainly introduces the implementation of heap sorting in JS, which has certain reference value. Now I share it with everyone. Friends in need can refer to

Preliminary knowledge of heap

• The heap is a complete binary tree.

• Complete binary tree: Except for the last layer of the binary tree, the number of nodes in other layers reaches the maximum, and all the nodes in the last layer are concentrated on the left (when the nodes on the left are full, Nodes can be missing only on the right).

• Big top heap: The root node is the maximum value, and the value of each node is greater than or equal to the value of its child node.

• Small top heap: The root node is the minimum value, and the value of each node is less than or equal to the value of its child node.

• Heap storage: The heap is implemented by an array, which is equivalent to a level-order traversal of a binary tree. As shown below:

#For node i, its sub-nodes The points are 2

i 1 and 2i 2 .

Heap sort algorithm

Now we need to sort the above binary tree in ascending order, which is divided into three steps:

1. Convert the initial binary tree into a large top heap (heapify). At this time, the root node is the maximum value and exchange it with the last node.

2. Except for the last node, convert the new heap composed of the remaining nodes into a large top heap. At this time, the root node is the sub-maximal value, and it is exchanged with the last node.

3. Repeat step 2 until the number of elements in the heap is 1 (or the length of its corresponding array is 1) and the sorting is completed.

This process is illustrated in detail below:

Step 1:

Initialize the large top heap, first select the last non-leaf node (we only need Adjust the size relationship between the parent node and the child node. The size relationship between the leaf nodes does not need to be adjusted). Assume the array is arr, then the subscript of the first non-leaf node is: i = Math.floor(arr.length/2 - 1) = 1, which is the number 4, as shown in the dotted box in the figure, find three numbers The maximum value is exchanged with the parent node.

Then, the subscript i is decremented by 1 in sequence (that is, starting from the first non-leaf node, traversing all non-leaf nodes from right to left, and from bottom to top). Every subsequent adjustment is the same: find the maximum value among the parent and child nodes and make an exchange.

After the numbers 6 and 1 are exchanged in this step, the order of the heap composed of numbers [1,5,4] is wrong, and one step of adjustment is required. Therefore, it is important to note that every time you make an adjustment to a non-leaf node, you must observe whether it will affect the sub-heap order!

After this adjustment, the root node is the maximum value, forming a large top heap, and the root node is exchanged with the last node.

Step 2:

Except for the current last node 6 (i.e. the maximum value), form a new heap of the remaining nodes [4,5,3,1] and convert it into a large top heap ( Pay attention to observation. At this time, other nodes except the root node all meet the characteristics of a large top heap, so you can start adjusting from the root node 4, that is, find the position where 4 should be).

Step 3:

Next repeat step 2 until The number of elements in the heap is 1:

##The number of elements in the heap is 1, sort Finish.

JavaScript implementation

// 交换两个节点
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，adjustheap 函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 adjustheap 操作，所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function adjustHeap(A, i, length) {
  let temp = A[i]; // 当前父节点
// j<length function>=0; i--) {
    adjustHeap(A, i, A.length);
  }
  // 排序，每一次for循环找出一个当前最大值，数组长度减一
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // 根节点与最后一个节点交换
    adjustHeap(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                         // 前最大值，不需要再参与比较，所以第三个参数
                         // 为 i，即比较到最后一个结点前一个即可
  }
}

let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);</length>

Program notes: Arrange the heap below node i into a large top heap. Note that the basis for this step is actually: assuming that the sub-heap below node i is already a large top heap. On the top heap, the function implemented by the adjustHeap function is actually to find the correct position of node i in the heap including node i. When doing the first heap later, a for loop is written in heapSort. Starting from the first non-leaf node, the adjustHeap operation is performed on each non-leaf node, so it is satisfied that in each adjustHeap, the node The sub-heap below i is already a large top-heap.

Complexity analysis: The adjustHeap function only traverses one node per layer of the heap, because
The depth of a complete binary tree with n nodes is [log2n] 1, so the complexity of adjustHeap The degree is O(logn), and the outer loop has f(n) times, so the final complexity is O(nlogn).

Application of heap

Heap is mainly used to implement priority queue. The following is an application example of priority queue:

• The operating system dynamically selects priority Supreme mission execution.

• In a static problem, to select the top M names among N elements, the complexity of using sorting is: O(NlogN), and the complexity of using priority queue is: O(NlogM).

The different complexities of implementing priority queues using ordinary arrays, sequential arrays and heaps are as follows:

Use heaps to implement priority Queues can make the complexity of joining and dequeuing very low.

The above is the entire content of this article. I hope it will be helpful to everyone's study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

JS implements merge sort

JS implements Hill sort

The above is the detailed content of JS implements heap sorting. For more information, please follow other related articles on the PHP Chinese website!