What is heap sort?

It refers to a sorting algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node

Understand the following concepts before reading this article

Complete binary tree: Every layer except the last layer is completely filled, and each layer is filled from left to right. It cannot be empty.

Heap: divided into big top heap and small top heap two kinds

Big top heap (small top heap) : can be divided into ordered region and unordered region, initially all unordered region

How are the steps performed?

  1. All it does is convert an unordered array to a big top heap (little top heap)

  2. Swaps the top value of the heap with the end value of the unordered array

  3. Adjust according to the nature of the heap to become a big top heap (small top heap)

  4. Then we continue with steps 1 to 3, over and over again until there are no values in the unordered region

At this point, one of the questions is, how do you distinguish between an ordered region and a disordered region? What is a big top heap (small top heap)? And how is the big top heap (small top heap) adjusted?

How do you distinguish an ordered region from a disordered region?

At the end of the loop it should look like this, no more unordered regions

The big top heap (small top heap) above is actually stored in an array like this

Now you know how to tell ordered from unordered, and how the big top heap is stored in an array

What is a big top heap (small top heap)?

You can see the difference between the big top heap and the small top heap.

Big top heap: Each node has a value greater than or equal to the value of its left and right children (in descending order)

Small top heap: The value of each node is less than or equal to the value of its left and right children (small to large order)

How is the big top heap (small top heap) adjusted?

This is the most difficult part of this article to understand. Here are the main steps:

Target: Unordered arrays (R1,R2…. Rn) to build the big top heap, that is, to complete the task

  1. Initially, all the values in the heap are in an unordered range

  2. The top element R[1] is exchanged with the last element R[n] in the unordered region, and a new unordered region (R1,R2,……) is obtained Rn-1) and the new ordered region (Rn)

  3. Since the new heap top R[1] after the swap may violate the heap properties, the current unordered region (R1,R2,……) is required Rn-1) adjusts to the new heap

  4. Then R[1] is again swapped with the last element of the unordered region to obtain a new unordered region (R1,R2…. Rn-2) and the new ordered region (Rn-1,Rn). Repeat this process until the number of elements in the unordered region is 0, and the whole sorting process is complete

conclusion

  1. The main operation is to construct the initial heap and adjust the heap.

  2. Each adjustment is from the parent node (I-1) / 2, left child node (2 _ I + 1), right child node (2 _ I + 2) to choose the largest node and the parent node to exchange position

Heap sort process

What is heap sort? Heap sort (big root heap)

The content/inspiration of the article is taken from below

  • Continuous maintenance/update 500+ front end questions/notes github.com/noxussj/Int…

  • [Big data visualization chart plug-in] www.npmjs.com/package/ns-…

  • [3D city modeling using three.js (Zhuhai)] 3D.noxussJ.top /