堆排序

步骤:

• 1.将数组调整成堆(从小到大排序用最大堆，从大到小排序用最小堆)

• 2.执行n次，将堆顶放到最后，忽略堆的最后元素,即堆大小-1，然后继续调整堆

为什么从小到大排序用最大堆，从大到小排序用最小堆呢？

这是根据堆的定义来出发的，如从小到大排序用最大堆。堆中的任意结点k都是比左子树和右子树的所有数大的，但是不能保证同层的结点的有序性，从这个性质出发，我们每次只能保证堆顶是最大的，所以我们直接放到堆的最后面即可。

$ 时间复杂度O(NlogN)，空间复杂度O(1) $

参考文献

算法基础课&浙大mooc数据结构

AC代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n , m;
int heap[N];
int sz = 0;

//向下调整
void down(int k){
    int t = k;
    if (k * 2 <= sz && heap[k * 2] > heap[t]) t = k * 2;
    if (k * 2 + 1 <= sz && heap[k * 2 + 1] > heap[t]) t = k * 2 + 1;
    if (t != k){
        swap(heap[k], heap[t]);
        down(t);
    }
}

int main(){
    //读入
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) cin >> heap[i];
    sz = n;

    //调整成最大堆
    for (int i = n / 2 ; i >= 1 ; i --){
        down(i);
    }


    //将堆顶放到最后，调整堆
    for (int i = 1  ; i <= n ; i ++) {
        swap(heap[1], heap[sz]);
        sz --;
        down(1);
    }

    //输出前m个数
    for (int i = 1 ; i <= m ; i ++) cout << heap[i] << " ";

    return 0;

}