堆

堆的结构：

一颗完全二叉树（十分平衡，除最后一层（叶结点）以外，其他节点均非空，最后一层从左到右依次排布）。

小根堆

也指最小堆。经过排序的完全二叉树，其中每一个非终端节点均小于其左右子节点，其根节点为所有元素的最小值。

大根堆同理。

存储方式

用一维数组维护堆状数据结构。

一号点为根节点。下标为x的节点，其左节点下标为2 * x，右节点下标为2 * x + 1。

基本操作

1.向下调整（down操作）:

若将一个数变大，则须将这个节点下移。以小根堆为例，将一个节点下移，则需要判断它与左右子节点的大小关系，并将它与（自己，左节点，右节点）三个数中的最小值交换。

void down(int u)
{
	int t = u; // 定义t，用来寻找三个数中最小值的下标。
    if (u * 2 <= size && h[u * 2] < h[u]) t = u * 2; // 判断左节点是否存在，且左节点是否更小。
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[u]) t = u * 2 + 1; // 同上，判断右节点。
    if (t != u) // 需要操作
    {
        swap(h[u], h[t]);
        down (t); // 递归操作，直到u为当前三个数的最小值。
    }
}

2.向上调整（up操作）：

同理，要将一个数变小，则需将这个节点上移，对于小根堆，上移操作仅需跟它的父节点比较即可。

void up(int u)
{
	while (u / 2 && h[u / 2] > h[u]){
		swap(h[u / 2], h[u]);
         u /= 2;
    }// 迭代操作，当为头节点或不能再向上时结束。
}

3.插入一个数：

将该数插入到整个堆的最后一个位置，然后进行up操作。

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

4.删除任意一个元素：

对于一维数组，删除数组的尾部非常简单，令size–即可，但若要删除中间元素，则需要整体改变下标的位置。

假设我们现在要删除第k个节点，只需将第k个节点变为最后一个节点，然后再删除最后一个节点。最后，对k节点进行down操作或up操作（因为此处第k个节点被赋给了最后一个结点的值），为了不用再进行判断，我们让k节点都进行up和down操作（不用担心会额外进行操作，当满足条件时，up操作和down操作只会执行其一）。

heap[k] = heap[size]; size -- ; down(k); up(k);// 删除头节点，将K改为1即可。

5.求集合中的最小（大）值：

对堆来说，最值即为根结点。

heap[1]; //大根堆为最大值，小根堆为最小值。

6.修改任意一个元素：

将要修改的元素（k节点）修改后，再进行一次up操作和down操作。

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

7.堆的构建

如果我们将n个元素每个都进行一次down操作，则时间复杂度为O（nlogn），也可通过优化，将复杂度改为O(n)。

堆的最后一层至多有n / 2个元素，如果我们要对所有元素进行down操作，则只需要对倒数第二层以上进行down操作，在对倒数第二层进行down操作时，也会保证处理到最后一层的元素，这样，我们就只须处理n / 2个数据，时间复杂度变为O(n)。

for (int i = n / 2; i ; i -- ) down(i);

进阶：堆的映射：

当我们把上述所提到的删除和修改第K个节点改为删除和修改第K个插入的数，就会变成更复杂的情况。

在这里我们需要额外开两个数组ph[N]和hp[N]，ph[k]用来存储第k个插入的数在堆中的下标，但仅有此并不够，当我们在进行up或down操作时，堆中的值会改变。

举个例子，当第5个插入的数在堆中的下标为3，其子节点在堆中的下标为6。那么ph[5]即为3，但此时小根堆是不稳定的，如果我们要进行一次down操作，会将heap[3]和heap[6]的值进行交换，此时第5个插入的数，即ph[5]就会改变。一句话来说，单单用ph数组对堆进行映射是单向的关系。

为了解决这种情况，我们另设一个数组hp[N]用来表示，第k个插入的数在堆中的下标在ph数组中的值。也就是说，用此数组将堆中的下标映射与ph数组，从而达到双向的关系。

ph数组与hp数组互为反函数。即ph[j] = k, hp[k] = j;

有这两个工具，我们就可以将down和up操作中的swap函数进行“升级”，即不仅仅改变堆中的两个值，他们所对应的插入关系也应该交换。

void heap_swap(int a, int b)
{
	swap(ph[hp[a]], ph[hp[b]]);
	swap(hp[a], hp[b]);
	swap(h[a], h[b]);
}

堆排序完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

void up (int u)
{
    while (u / 2 && h[u / 2] > h[u]){
        swap(h[u], h[u / 2]);
        u >>= 1;
    } 
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;

    for (int i = n / 2; i ; i --) down(i);

    while (m -- ){
        printf("%d ", h[1]);
        h[1] = h[cnt -- ];
        down(1);
    }

    return 0;
}