Heap parsing and heap sorting

Pile up

The basic structure

The heap is a complete binary tree

1. Except for the last floor, it is full

2. The nodes of the last layer are in order from left to right

example ：

Small cap pile ： The value of each node is less than （ be equal to ） Values of left and right child nodes

Here is a small top pile

Storage

Use an array to store . Subscript from 1 Start , The root node is 1. If a node is x, Then the left son is 2x, The right son is 2x+1（ Subscript from 0 At the beginning 2x+1,2x+2）

operation

（ Take the small root pile for example ）

Two basic operations

down sinking ：

For example, after modifying the value of the root node , It needs to be readjusted , Then you need to compare the size of this point with the value of the two child nodes , Choose the smaller one to exchange with , Take this point down again and continue to compare , And so on

up rising ：

Same thing ： For example, modify the value of the last node , I need to compare it with its parent node , If it is less than the value of the parent node , In exchange for . And so on

Time complexity analysis of two basic operations ： Both operations are proportional to the height of the tree , So all for logn

Five operations ： use down,up Operation to achieve

1. Insert a number . Insert... At the end , Conduct up operation
2. For the minimum . Directly the root node
3. Delete minimum . Delete root node , Put the last node at the root node ,down operation
4. Delete any element . Put the last node in this position ,down,up（ There are three situations , Immobility 、 Go up or down , although down,up With the , But there is only one case , Only one ）
5. Modify any element , In the same way ,down,up

One heap Array ,size Indicates the current heap size .

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≤m≤n≤1e5,
1≤ The elements in the sequence ≤1e9

sample input ：

5 3
4 5 1 3 2

sample output ：

1 2 3

Ideas ：

A property of complete binary tree is used , Subscript from 1 Start , Subscript <= n / 2 All nodes of are non leaf nodes , Greater than n / 2 All are leaf nodes , We start with non leaf nodes and move forward one by one down operation . The heap top is the smallest value at present , The value of taking out the top of the heap every time is the minimum value , And carry out the above 5 Of the operations 3 Operations , That is, delete the minimum , Refactoring heap .C++ The code implementation is as follows

Code ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, m, s;
int h[N];

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

int main()
{
    
    cin >> n >> m;
    s = n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    for (int i =  n / 2; i >= 1; i -- ) {
    
        down(i);
    }
    while (m -- ) {
    
        printf("%d ", h[1]);
        h[1] = h[s -- ];
        down(1);
    }
    return 0;
}