heapsort

Heap sort

Heap sort is a sorting algorithm designed using the data structure of a heap. Heap sort is a selection sort. Its worst and best, The average time complexity is O(nlogn), which is also unstable sorting. First, let’s briefly understand the heap structure.

Heap

A heap is a complete binary tree with the following properties: the value of each node is greater than or equal to its left and right children The value of a node is called a big top heap; or the value of each node is less than or equal to the value of its left and right child nodes, which is called a small top heap.

Recommended courses: PHP Tutorial.

As shown below:

#At the same time, we number the nodes in the heap by layer and map this logical structure It looks like this in the array

The array is logically a heap structure. We use a simple formula to describe the definition of the heap:

Large top heap: arr[i] >= arr[2i 1] && arr[i] >= arr[2i 2]

Small top heap: arr[i]

The basic idea of ​​heap sorting is:

Construct the sequence to be sorted into a big top Heap, at this time, the maximum value of the entire sequence is the root node at the top of the heap. Swap it with the last element, then the last value is the maximum value. Then reconstruct the remaining n-1 elements into a heap, so that the next smallest value of n elements will be obtained. If you execute this repeatedly, you can get an ordered sequence

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