838. Heap sorting

subject

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≤105,
1≤ The elements in the sequence ≤109
sample input ：
5 3
4 5 1 3 2
sample output ：
1 2 3

Ideas

Ideas ：
Common operation of heap ：
1. Insert a number h[++size] = num; up(size);
2. Find the minimum value in the set h[1];
3. Delete minimum h[1] = h[size];size--; down(1);
4. Delete any element h[k] = h[size]; size--; down(k), up(k);//down and up Do it all once , Only one , There is no need to judge and execute , Convenient code writing and memory
5. Modify any element h[k] = num; down(k), up(k); //down and up Do it all once , Only one , There is no need to judge and execute , Convenient code writing and memory

Code ：

#include <iostream>

using namespace std;

const int N = 100010;

int h[N], cnt; 

// The array stores the nodes of the heap , Subscript from 1 Start ,  node x The subscript of the left child node of is 2x, The subscript of the right child node is 2x+1
// If subscript from 0 Start , node x The subscript of the left child node of is 2x+1, The subscript of the right child node is 2x+2


//down operation , Subscript in the heap as u To reorder the elements of 
//down The core idea of is node x, node 2x, node 2x+1 Exchange positions , Ensure that the minimum of the three values is at the parent node 
void down(int u)
{
    
    int t = u;
    if(2 * u <= cnt && h[2 * u] < h[t]) t = 2*u;
    if(2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    if(t != u)
    {
    
        swap(h[t], h[u]);
        down(t);
    }
}

int main()
{
    
    int n, m;
    cin >> n >> m;
    
    cnt = n;// Number of nodes in the heap , That is, the total number of sequence elements 
    
    for(int i = 1; i <= n; i++)
        cin >> h[i];
    
    // Generate small root heap , The time complexity is about O(n),  from n/2 The node at starts to traverse the node up , And do it one by one down(i) operation , Every time down perhaps up The operation is proportional to the number of levels of the binary tree , The time complexity of each operation is logN
    for(int i = n/2; i; i--)
        down(i);
    
    while(m --)
    {
    
        cout << h[1] <<' ';
        h[1] = h[cnt];
        cnt--;// The number of heap elements decreases automatically 
        down(1);// Will exchange the top elements down Reorder into small root piles 
    }
    return 0;
}