题目描述

输入一个长度为n的整数数列，从小到大输出前m小的元素；

样例

5 3
4 5 1 3 2

1 2 3

算法1

堆排序

像这种找前m小元素的题就是用堆；

堆的本质是一棵完全二叉树，对每一个堆中的节点，要求它的两个子节点都要不大于它(小顶堆)或不小于它(大顶堆)；堆顶元素从1算起比从0算起更便于查找其子节点和父节点；堆的核心算法有两个(以小顶堆为例)：
1. 向下调整，即给定一个节点，检查其与两个子节点的大小关系，如果子节点比父节点小，则把子节点中较小的那一个与父节点交换；若发生了交换，则递归向下执行向下调整操作；

void down(int k){
    int t = k;
    //t 等于 2*k 和 2*k+1 中较小的那一个节点；
    if(2*k <= size && heap[2*k] < heap[t]) t = 2*k;
    if(2*k+1 <= size && heap[2*k+1] < heap[t]) t = 2*k+1;
    if(t != k) {swap(heap[t], heap[k]); down(t);}
}

1. 向上调整，即给定一个节点，比较它与父节点的大小关系，如果比父节点小，则与父节点交换，递归向上执行向上调整操作；

void up(int k){
    if(k/2 > 0 && heap[k] < heap[k/2]){
        swap(heap[k], heap[k/2]);
        up(k/2);
    }
}

一般来讲堆的经典操作有如下几种：
1. 建堆：建堆一般从最后一个元素的父节点(size/2)开始，对该节点及它之前的每一个节点，都执行向下调整操作；

for(int i = size/2; i > 0; --i) down(i);

1. 插入元素：将该元素插入到堆的末尾，然后对其执行向上调整操作；

heap[++size] = x; up(size);

1. 删除元素：将堆的最后一个元素把堆顶元素覆盖，然后对其执行向下调整操作；

heap[1] = heap[size--]; down(1);

1. 查询最小(最大元素)：直接输出堆顶元素；

return heap[1];

还有：
5. 修改任意一个元素：修改完之后对其执行向下调整和向上调整操作(因为只可能比原来大或者比原来小，所以只会执行这两操作中的一种)；

heap[k] = x; down(k); up(k);

1. 删除任意一个元素：用堆的最后一个元素把该元素覆盖，然后对其执行向下调整和向上调整操作；

heap[k] = heap[size--]; down(k); up(k);

时间复杂度

1. 建堆：O(n); 假设有N个元素，则堆高度为H = log2N + 1; 最后一层的父节点最多向下调整1次，共有2^(H-2)个， 倒数第二层父节点最多向下调整2次，共有2^(H-3)个， 顶点最多向下调整H-1次，共有2^0个，故时间复杂度s = 1 * 2^(H-2) + 2 * 2^(H-3) + … + (H-2) * 2^1 + (H-1) * 2^0, 将H = log2N+1带入后，得s = 2N - 2 - log2N;
   故近似时间复杂度为O(N);
2. 插入元素：插入元素每次执行向上调整操作后都会向上走一层，所以与堆的高度息息相关，最多向上执行H-1次up(k)操作，故时间复杂度为O(log2N);
3. 删除元素：向下最多执行H-1次向下调整操作，故时间复杂度为O(log2N)；
4. 查询最大/最小元素:O(1);
5. 修改任意元素：对该元素而言，只会执行向上调整和向下调整的一种，故时间复杂度O(log2N);
6. 删除任意元素：同上，O(log2N);

C++ 代码

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

const int N = 1e5+7;
int heap[N], sz;                            //size为关键字，所以换成sz表示堆的大小；

void down(int k){
    int t = k;
    //t 等于 2*k 和 2*k+1 中较小的那一个节点；
    if(2*k <= sz && heap[2*k] < heap[t]) t = 2*k;
    if(2*k+1 <= sz && heap[2*k+1] < heap[t]) t = 2*k + 1;
    if(k != t){
        swap(heap[t], heap[k]);
        down(t);
    }
}

int main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; ++i) cin>>heap[i];
    sz = n;

    for(int i = n/2; i > 0; --i) down(i);   //建堆

    while(m--){                             //每次输出堆顶元素后，删除该元素；
        cout<<heap[1]<<' ';
        heap[1] = heap[sz--];
        down(1);                            //删除堆顶元素需执行向下调整；
    }
    return 0;
}