An overview of the

So before we talk about heap sorting, what is a heap and what is a maximum heap and what is a minimum heap

What is a pile of

The heap here is not a heap in a stack, but a data structure.

A heap can be thought of as a complete binary tree. One of the “nice” properties of a complete binary tree is that every layer except the lowest is full. This allows the heap to be represented as an array, with each node corresponding to an element in the array, as shown below:

The maximum heap

A maximum heap is a heap in which each parent node has an element value greater than or equal to its child node (if any)

Obviously, the largest element value in the largest heap occurs at the root (the top of the heap)

The minimum heap

A minimum heap is a heap in which each parent node has an element value less than or equal to its child node (if any)

Therefore, the smallest element value in the smallest heap occurs at the root (the top of the heap)

The relationship between an array index and a node

Parent (I) = (i-1)/2 left(I) = 2i+1 rigth(I) = 2i+2Copy the code

Heap sort idea

The sequence to be sorted is constructed as a big top heap, in which the maximum value of the entire sequence is the root node at the top of the heap. Swap it with the trailing element, where the trailing element is the maximum. The remaining n-1 elements are then reconstructed into a heap, which yields the subsmallest values of n elements. Do this repeatedly, and you get an ordered sequence

The time-space complexity of heap sort is as follows:

Java code implementation

The code below is the implementation of the above idea. The comments are already very detailed.