Manually implement heap sorting -838 Heap sort

Heap properties

Pile up （Heap） Is a kind of data structure , They have a tree structure , And it can ensure that the parent node is larger than the child node （ Or small ）. When the root node saves the maximum value in the heap , be called Big root pile ; conversely , It is called a Heap .

Binary heap （Binary Heap） It's the simplest 、 Common heap , It is a tree that conforms to the nature of heap Perfect binary tree . It can achieve O(logn) Insert or delete a value , also O(1) Query the largest （ Or the smallest ） value .

Storage

Take the small root pile for example
As a complete binary tree , A binary stack can be used 1-index To store , For the node p,p2 That is, the left son ,p2+1 That is, the right node . meanwhile , use size Record the number of nodes in the current binary heap .

The relevant operation

up(int x)： Compare with the root node of the current node , If the current point is smaller than the root node , Exchange with the root node
down(int x)： Compare with the left and right sons of the current node , If the left and right sons are a little smaller than the current , Then exchange the younger son with the current point

Templates

// h[N] Store values in the heap , h[1] It's the top of the pile ,x My left son is 2x,  The right son is 2x + 1
// ph[k] Store the k The position of an insertion point in the heap 
// hp[k] The subscript in the heap is k Which point is inserted 
int h[N], ph[N], hp[N], size;

//  Swap two points , And its mapping relationship 
void heap_swap(int a, int b)
{
    
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
    
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    
    while (u / 2 && h[u] < h[u / 2])
    {
    
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n) Building the heap 
for (int i = n / 2; i; i -- ) down(i);

subject

Code

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100005;
int h[N],len;
int n,m;

void down(int u){
    
    int t=u; //t Save the subscript of the lowest decimal 
    if(2*u<=len && h[2*u]<h[t]){
      // Subscript to be u My point has a left son , The left son is smaller 
        t=2*u;   // The youngest is the left son 
    }
    if(2*u+1<=len && h[2*u+1]<h[t]){
      // Subscript to be u The right son of is smaller than the current youngest 
        t=2*u+1;  // The youngest is the right son 
    }
    if(u!=t){
       // If the current value is not the minimum , So update 
        swap(h[u],h[t]); // Exchange the smallest to u The location of 
        down(t); // Recursive current （2u+1） The following values 
    }
}

void up(int u){
    
    if(u/2>=1 && h[u/2]>h[u]){
      // There is a parent node ,
        swap(h[u/2],h[u]);
        up(u/2);
    }
}

int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    
        cin>>h[i];
    }
    len=n;
    for(int i=n/2;i>0;i--){
     // Because the last layer has no child nodes , So just cycle n/2 That's it .
        down(i);
    }
    
    while(m--){
    
        cout<<h[1]<<" ";
        h[1]=h[len];  // After taking out the minimum value , Put the last value in the first position , Total number minus one , then down
        len--;
        down(1);
        
    }
    return 0;
}

Reference resources Algorithm learning notes (47): Binary heap