给定一串数，在有频繁的加入删除操作时，如何维护它们的最大值和最小值?
        经典的O(n)做法即为遍历整个数组，找到最值。这种方法简单但效率低下。
        堆积树是一种基于完全二叉树的数据结构，可以在O(logn)的时间复杂度下维护序列最值。

堆积树的特点是:
        1 是一棵完全二叉树
        2 每一个节点的值都大于(或小于)其儿子节点的值
        节点值大于儿子节点的为大根堆，小于即为小根堆。显然，在根节点处可以取到最值。
        下面谈论堆的构造与维护算法(以小根堆为例)。
        先讲堆的节点交换算法，它的作用是在两棵子树已经为堆的基础上将这棵树转化为堆积树。 节点的交换算法是堆的基本算法。算法的步骤是先找到根节点与两个儿子节点的最小值，将根节点与最小值所在节点交换。此时根节点所在的局部具有小根堆性质。倘若一开始根节点就最小，依照算法的前提(两棵子树已为堆)，此时堆积树构造完毕，算法结束。但是倘若根节点起初不是最小值，交换后参与交换的子树由于根节点值变大，小根堆性质可能局部被破坏，但是由于该子树的两棵子树仍为堆，符合算法前提，再对该子树进行同样的递归操作，直到树的叶子节点。此时整棵树已经成为小根堆。
        该算法的示例代码如下:

1
2
3
4
5
6
7
8
9
10
void solve(int x) {
    if (x > n)return;
    int l1 = 2 * x, l2 = 2 * x + 1, l = x;
    if (l1 <= n && heap[l1] < heap[l])l = l1;
    if (l2 <= n && heap[l2] < heap[l])l = l2;
    if (l != x) {
        swap(heap[l], heap[x]);
        solve(l);
    }
}

        堆的构造过程即为从堆的最后一个非叶子节点开始，直至根节点，顺次执行堆的节点交换算法。由完全二叉树的性质易得这个非叶子节点编号为n/2(n为节点数量)。
        示例代码如下:
1
2
3
void build() {
    for (register int i = n / 2; i >= 1; i--)solve(i);
}

        从节点交换算法定义上不难理解这个方法的可行性。
        如何找到最小值并将其删除?
        由上文讨论，heap[1]即为最小值。删除该元素只需将堆中最后一个元素覆盖到根节点处并令节点数减一，再在根节点处调用节点交换函数。
        代码如下:
1
2
3
4
5
6
int top() {
    int t = heap[1];
    heap[1] = heap[n--];
    solve(1);
    return t;
}

        向堆中添加一个元素只需在堆的末尾加上该元素，该重新构造一遍堆即可。这个方法可行，但不最优。这里介绍一种更高效的算法。
        由于此时除了该元素之外，其余均维持小根堆性质。所以只需将该元素“上浮”，即将该元素与其父节点比较，若其比父节点值小，交换两个节点，从父节点开始继续上浮，直到父节点不比其大或者到达根节点时为止。
1
2
3
4
void up(int x) {
    if (x == 1)return;
    if (tree[x] < tree[x / 2])swap(tree[x], tree[x / 2]), up(x / 2);
}

        大根堆类比即可。
        由于堆可以维护最值，可以将其与选择排序算法结合，形成一种时间复杂度为O(nlogn)的新算法，称为堆排序算法。堆排序是不稳定的排序算法。算法思想是先将数据构造成堆，从中不断选出最值，再将其从堆中删除，重复该过程直到堆为空，此时即可获得有序的序列。