AcWing 838. 堆排序

题目传送门

一、堆的数据结构

堆是一个完全二叉树:除了最后一层结点以外，上面的每一层都是满的。最后一层的结点是从左到右排布的。

小根堆：每一个点都是小于左右儿子的,所以根节点就是树中最小值.或者叫小顶堆。

存储方式：全新的存储方式，用一维数组来存。因为是完全二叉树，所有数据的下标是有规则可以找到的。

位置(x) 左儿子(2x) 右儿子(2x+1)

下标是从(1)开始的，从(0)开始不方便，因为(2x)还是自己没法玩。

二、图解说明

三、手写一个堆（小根堆）

前三个操作就是(STL)里堆支持的操作

1、插入一个数

    heap[++sz]=x; //在一维数组最后一个位置填充x
    up(sz);       //将最后一个元素不断上移

2、求最小值

    heap[1]

3、删除最小值

    heap[1]=heap[sz--]; //就是把尾部最后一个元素替换掉头元素，然后sz--
    down(1);              //然后再down(1)就行了

以下两个操作STL无法实现或者说无法直接实现

4、删除任意一个元素

    heap[k]=heap[sz--];
    down(k);
    up(k);   //其实只能执行一个，因为大了向下走。小了向上走嘛

5、修改任意一个元素

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

两个基本操作,这两个操作结合起来就能完成上面五个操作。
(down(x)) ---> 向下调整
(up(x)) ---> 向上调整

四、完整代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

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

/**
 * 功能:向下移动
 * @param u
 */
void down(int u) {
    int t = u;
    if (u * 2 <= sz && heap[u * 2] < heap[t])t = u * 2;
    if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
    if (u != t) {
        swap(heap[u], heap[t]);
        down(t);
    }
}
/**
 * 功能：向上移动
 * @param u
 */
void up(int u) {
    //如果父节点存在，并且父节点值大于u节点值
    while (u / 2 && heap[u / 2] > heap[u]) {
        swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}


int main() {
    //读入优化
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> heap[i];
    sz = n;

    //如何初始化堆
    //这是一个小技巧，建堆的技巧O(N),其实也可以是int i=n;i>0;i--,但最后一层再down没有意义，省略
    for (int i = n / 2; i; i--)down(i);

    //遍历提取出来
    while (m--) {
        printf("%d ", heap[1]);
        //删除堆顶
        heap[1] = heap[sz--];
        //再down一次
        down(1);
    }
    return 0;
}