2. Heap sort "hard to understand sort"

Heap sort （Heapsort） It is a sort algorithm designed by using the data structure of heap . This heap is an approximately complete binary tree structure , And it's also a big pile , Sorting is also based on this big top heap .

Why do you say Heap sort It's hard to understand ？ answer ： The main reason is some people Maybe not Binary tree , I don't know what is Pile up , Never learned The idea of simulating arrays . in other words He doesn't have these In the case of premise knowledge points , How is that possible? Good understanding Heap sorting . What's more? Heap sort Adjust the implementation of the heap , also Yes Our biggest recursion . and Overall sorting idea , once lecturer I didn't make it clear , Probably Just Is a little knowledge .

1.1 Algorithm description

• Use array to simulate binary tree structure , Make the left and right nodes of each root node The corresponding subscript is left = 2k + 1、right = 2k + 2.
• Put this binary tree Initialize to Big pile top , Here be used Recursive operation . Thought is Start with the last subtree , forward Put each subtree All become big piles ！ Of course there will be Aftereffect problem （ namely When we After adjusting the node order , The node being exchanged The subtree that is the root node Is it still Big top pile ？？）, therefore We here Need recursive , then Go to Handle All subtrees under this node .
• because Root node of the entire binary tree yes Maximum value , So we Sure hold This node and Last A node swapping . namely stay 1 ~ n Within the range of nodes , This The root node yes Maximum , We will take it. Put it in Last . then Let's put 1 ~ n – 1 A binary tree with a range of nodes （ exclude The last node ） Let it become Big pile top , then Go again Conduct The above operations , Put the penultimate Maximum Put it in The penultimate position . And so on , When we Only The first node of the binary tree , Then the whole Orderly ！！

---

1.2 Dynamic diagram demonstration

---

1.3 Code implementation

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

vector<int> arr = {
    91,60,96,13,35,65,46,65,10,30,20,31,77,81,22};

int len;

void swapF(int k){
    //  To  k  by   The root node   The subtree of   Conduct   Explore   and   adjustment 
  int left = 2 * k + 1;
  int right = 2 * k + 2;
  
  int father = k;//  To be updated   The root node , Probably   The root node   need   Adjust and update 
  
  if(left < len && arr[left] > arr[father]){
    
    father = left;//  The left node   Than   The root node   Big , therefore   The subscript of the left node   Save to 
    // father  in , advance   get set   Location of the root node 
  }
  
  if(right < len && arr[right] > arr[father]){
    
    father = right;//  if   The largest node   yes   Right node , that  father = right
  }
  
  if(father != k){
    //  If   The subtree is   adjustment , namely   The root node   change 
    //  then   Handle   Aftereffect problem 
    swap(arr[father],arr[k]);//  First the   Adjust this subtree 
    swapF(father);//  then   Come on   look down   The location of the node we exchanged   The data has changed 
    //  After change , whether   also   keep   Piled on top   nature 
  }
}

void init(){
    
  len = arr.size();
  for(int i = floor(len / 2);i >= 0; i--){
    //  from   the last one   Subtree start 
    swapF(i);
  }
}

void heapSort(){
    
  init();
  for(int i = len - 1;i > 0;--i){
    
    //  Conduct   Sort , Take every one.   Within the interval   Maximum value , all   Put it in   Where to put it 
    swap(arr[i],arr[0]);
    len--;
    swapF(0);
  }
}

int main(void){
    
  heapSort();
  for(auto x : arr){
    
    cout << x << " ";
  }
  return 0;
}

Heap sort In two parts ： Adjustment of pile + The order of the heap .

Time complexity ：O(n) + O(nlogn) = O(nlogn)

Spatial complexity ：O(1)