What is heap sort?

A kind of sorting algorithm designed using the data structure heap. A heap is an almost complete binary tree structure, while satisfying the property of a heap: the key or index of a child node is always smaller (or greater) than that of its parent node

Understand the following concepts before reading this article

Complete binary tree: Every layer except the last one is completely filled, and every layer is filled from left to right with no gaps (just like this structure, so I won’t use it in this article).

Heaps: There are two types of large top heaps and small top heaps

Large top heap (small top heap) : can be divided into ordered region and disorder region, initially all are disorder region

How do the steps of execution work?

  1. All it does is convert an unordered array to a large top heap (small top heap)
  2. Swap the position of the value at the top of the heap and the end of the unordered array
  3. Adjust to the nature of the heap, becoming a large-top heap (small-top heap)
  4. Then continue steps 1 and 3, and so on, until the unordered region has no value

Now, the question is, how do you distinguish between an ordered region and a disordered region? What is a large top heap (small top heap)? And how is the large top heap (small top heap) adjusted?

How to distinguish between ordered and disordered regions?

<img src=”https://noxussj.top:3000/27/1.png”></img>

<img src=”https://noxussj.top:3000/27/2.png”></img>

It should look like this at the end of the loop. There is no unordered region

<img src=”https://noxussj.top:3000/27/3.png”></img>

The large top heap (small top heap) above actually looks like this when stored in an array

Now you know how to distinguish between ordered and unordered regions, and how to store a large top heap in an array

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

<img src=”https://noxussj.top:3000/27/4.png”></img>

You can see the difference between a large top stack and a small top stack.

Large top heap: The value of each node is greater than or equal to the value of its left and right children (large to small array)

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

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

Also the most difficult part of this article, here is a brief description of the main steps:

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

  1. Initially, all values in the heap belong to the unordered region
  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 swapping may violate the nature of the heap, the current unordered region (R1,R2,……) needs to be analyzed Rn-1) is adjusted to the new heap
  4. Then we exchange R[1] with the last element of the unordered region again to get a new unordered region (R1,R2….) Rn-2) and a new ordered region (rn-1,Rn). This process is repeated until the number of elements in the unordered area is 0, then the sorting process is complete

conclusion

  1. The main operation is to construct the initial heap and adjust the heap.
  2. Each adjustment is made from the parent node (i-1) / 2, the left child node (2)I + 1), right child node (2I + 2) The largest of the three nodes will exchange its position with its parent node

<img src=”https://noxussj.top:3000/27/5.gif”></img>

Heap sort procedure

Comics: What is heap sort? What is heap sort? Heap sort (large root heap)

additional

  • This article is published through multiple platforms of “We Media” and will not be maintained after publication. If you have any objection to the content, you can discuss it in the GitHub below
  • The ongoing maintenance / 500 + face questions before update/notes 】 https://github.com/noxussj/In…
  • [3D city modeling using three. JS (Zhuhai City)] https://3d.noxussj.top/