How to sort in heap sort

1. Construct the initial heap:

When initializing the heap, all non-leaf nodes are filtered. .

The subscript of the last non-terminal element is [n/2] rounded down, so filtering only needs to start from the [n/2]th rounded down element and adjust from back to front.

For example, given an array, first construct a complete binary tree based on the array elements.

Then starting from the last non-leaf node, comparison and exchange are performed from the parent node, left child, and right child each time. The exchange may cause the child node to not satisfy the properties of the heap, so every time After this exchange, the exchanged child nodes need to be readjusted.

2. Perform heap sorting:

After you have the initial heap, you can sort it.

Heap sort is a selection sort. The initial heap created is the initial unordered area.

When sorting starts, the top element of the heap is output first (because it is the highest value), and the top element of the heap and the last element are exchanged. In this way, the nth position (that is, the last position) is used as the ordered area, and the previous The n-1 positions are still unordered areas. Adjust the unordered area. After obtaining the heap, exchange the top and last elements of the heap so that the length of the ordered area becomes 2. . .

Continue this operation, re-adjust the remaining elements into the heap, and then output the top element of the heap to the ordered area. Each swap results in an unordered area of ​​-1 and an ordered area of ​​1. This process is repeated until the length of the ordered area grows to n-1 and the sorting is completed.

3. Heap sorting example:

First, establish the initial heap structure as shown:

Then , exchange the element at the top of the heap and the last element. At this time, the last position is used as an ordered area (the ordered area is shown in yellow), and then adjust the heap of other unordered areas. After regaining the big top heap, exchange the top and last elements of the heap. The position of the penultimate element...

Repeat this process:

Finally, the ordered area expansion is completed That is, the sorting is completed:

#It can be seen from the sorting process that if you want to get ascending order, create a large top heap, and if you want to get descending order, create a small top heap.

The above is the detailed content of How to sort in heap sort. For more information, please follow other related articles on the PHP Chinese website!