当前位置:网站首页>Heap sort

Heap sort

2020-12-06 15:28:14 He's very handsome at the age of five

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 :

Binary heap : It's a complete / Complete binary tree

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)

​ Maintaining heap characteristics

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

 

 

 
 

版权声明
本文为[He's very handsome at the age of five]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206152638720f.html