# Heap sort

2020-12-06 15:28:14

## introduce ：

Heap sort is an in place algorithm , The worst time complexity of the algorithm is O(nlogn)

Algorithm design technology ： Pile up (heap) To speed up , Priority queue ,ADT

## To know what heap sorting is , You have to understand the heap first , Let's start with the heap ：

### Node number from 1 The starting pile

Perfect binary tree ( node i)
Incomplete binary tree
father i/2     Left the child 2i     The right child 2i + 1    （ Simple comparison

2. Node number from 0 Start

father （i-1）/2     Left the child 2i + 1     The right child 2i + 2 ​（ A little more complicated ）​

​ Array form      Implicit heap

### ​​ The biggest pile ( Big root pile )/ The smallest pile ( Heap )

The biggest pile ( Big root pile )

The characteristics of the big root heap ：

1. ​A[i/2] >= A[i]     The biggest pile ( Big root pile )
2. i/2 For the node i Father
3. Top of pile / The biggest element
4. It's like chaos      Perfect chaos

The smallest pile ( Heap )

The characteristics of the small root heap ：

1. A[i/2] <= A[i]     The smallest pile ( Heap )
2. i/2 For the node i Father
3. Top of pile / The smallest element

## The operation of the binary stack ：

• Adjust the node i To satisfy the heap characteristics O(logn)
• Building the heap O(n)
• Heap sort O(nlogn)
• Insert elements O(logn)
• Take out the largest element O(logn)
• To a node i Promotion O(logn)
• The biggest dollar O(1)

### node i The sinking of      Other nodes meet the requirements ( The characteristics of the heap )

1. Let the node be 4 The value of is taken out of the heap

2. Separately 4 Compared with its left and right children , because 14 > 7 > 4, So the 14 Put it in 4 In the right place

3. Continue with the original 14 Position left and right children compare , because 8 > 4 > 2, So the 8 Put it in the original 14 The location of , hold 4 Put it in the original 8 The location of

https://chowdera.com/2020/12/20201206152638720f.html