Heap sort [handwritten small root heap]

One 、 What is a heap ？

Heap is an efficient priority queue , We can think of the heap as an array of complete binary trees .
nature ：

• The value of a node in the heap is always not greater than or less than the value of its parent node
• The heap is always a complete binary tree

The heap with the largest root node is called maximum heap or large root heap , The heap with the smallest root node is called the smallest heap or small root heap .

Algorithm idea and operation （ Take the small root pile for example ）：

Put all the values to be sorted into each node of a complete binary tree , At this time, the binary tree does not have the nature of heap , utilize up perhaps down Operation to adjust the heap .

During the creation of the heap , We need to add two operations ：

• Upward adjustment method （up）【 Building the heap 】
  Adjust from the last node , Compare with its parent node , If it is smaller than the parent node , It does not conform to the nature of small root pile , So we need to exchange , Otherwise, there is no need to exchange .
  After adjusting to a node , Regard the parent node of this node as the current node , Continue to make adjustments .
  And so on , It can be adjusted into piles .
• Downward adjustment method （down）
  Set the parent node to fa, Left son for l, The right son is r.
  From the last non-leaf node （ That is to say n/2 Nodes ） Start , use fa Respectively with l and r The comparison , The youngest son in exchange , If fa Is already the smallest , There is no need to exchange .
  The same as the upward adjustment method , After adjustment , From the youngest son as fa, Continue to do downward adjustment .

Why start with the last non leaf node down Well ？

The value in the figure is the node number , Altogether 9 Nodes , that n=9, So from n/2 Start adjusting from the fourth node （ Red nodes ）.
Why is that ？
Because what we do is down operation , So in order to adjust to all points , It must be adjusted to the last leaf node . It happens that the parent node of the last leaf node is the n/2 Nodes , from n/2 Nodes start down, It will definitely adjust to all points .

Let's take a look at the simulation process ：

Initial state diagram

Now we have built a small root pile （ Note that small root pile and large root pile are not unique , Just meet the nature ）

Next, use the heap to sort ：

subject ： Heap sort

Enter a length of $n$ The whole number sequence of , From small to large, before output $m$ Small number .

Input format
The first line contains integers $n$ and $m$.

The second line contains n It's an integer , Represents an integer sequence .

Output format
All in one line , contain $m$ It's an integer , Represents the first in an integer sequence m Small number .

Data range
$1\le m\le n\le 105$,
$1\le CountColumninelementplain\le 109$
sample input ：

5 3
4 5 1 3 2

sample output ：

1 2 3

Topic ideas ：

This question is to output the top k Number , Because heap is not guaranteed from left to right 、 The order from top to bottom is increasing , For example, the third number in the figure below is 5, Actually, the third number should be 4, So we can't build a heap and output it directly before k A digital .
So you can delete nodes （ It's not really deletion ） To implement heap sorting , Which node is more appropriate to delete , Obviously, it can't be the front and middle nodes , Because deleting the previous node in the heap is very troublesome , But deleting the last node is easy . Can I delete the last node ？ The answer is yes , Because the top element is guaranteed to be the smallest , So every time you output the top of the heap element, you can exchange the top of the heap element with the last element , At this time, the smallest element becomes the last element , You can delete it （ I can't use it anymore ）, Then start with the top element down operation , Therefore, we can find that the nature of the heap can still be maintained , So you can delete the last node to sort the heap .

Heap storage ：
In order to facilitate storage and implementation , Heaps can usually be modeled using arrays .
fa： Parent node ,l： Left second son ,r： Right son
set up $fa=x$, be $l=2\ast x$,$r=2\ast x+1$

AC Code （C++）：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+10;
int q[N],numbers,n,m;

void down(int x){
    
    int t=x;
    if(x*2<=numbers && q[x*2]<q[t]) t=x*2;
    if(x*2+1<=numbers && q[x*2+1]<q[t]) t=x*2+1;
    if(t!=x){
    
        swap(q[t],q[x]);
        down(t);
    }
}

int main(){
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&q[i]);
    numbers=n;  // The number of remaining nodes after deleting a node 
    for(int i=n/2;i;i--) down(i);
    while(m--){
    
        printf("%d ",q[1]);
        q[1]=q[numbers];
        numbers--;
        down(1);
    }
    return 0;
}