n个整数中输出其中最小的k个——堆排序

• 1读入数据；
• 2建堆，大小为k；
• 3后续数据选择较小的插入堆中；
• 4打乱堆排序，从小到大排序进行输出。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 0, k = 0;
    while(cin >> n >> k)
    {
        vector<int> vec;
        int num = 0;
        while(n--)
        {
            cin >> num;
            vec.push_back(num);
        }
        //建堆k*logk
        vector<int> heap(vec.begin(), vec.begin() + k);
        make_heap(heap.begin(), heap.end(), less<int>());
        //插入(n - k)*logk
        for(int i = k; i < vec.size(); i++)
        {
            if(vec[i] < heap[0])
            {
                //插入一个更小的
                heap.push_back(vec[i]);
                push_heap(heap.begin(), heap.end());
                //弹出一个最大的
                pop_heap(heap.begin(), heap.end());
                heap.pop_back();
            }
        }
        //从小到大输出,k*logk + k
        sort(heap.begin(), heap.end());
        for(int i = 0; i < heap.size(); i++)
        {
            cout << heap[i];
            if(i != heap.size() - 1)
            {
                cout << " ";
            }
        }
        cout << endl;
    }
}