二叉堆

二叉堆首先是完全二叉树，二叉堆的存储方式和完全二叉树的顺序存储一致（详见树和图的存储结构），d表示二叉堆最后一个已用位；

int heap[n], d = 0;

下面的up和down操作都假设是小顶堆；

如果某个结点的值变小，则需要向上调整：

void up(int x) {
    while (x/2 >= 1 && heap[x] < heap[x/2]) {
        swap(heap[x], heap[x/2]);
        x /= 2;
    }
}

如果某个结点的值变大，则需要向下调整：

void down(int x) {
    int t = 2*x;
    while (t <= d) {
        if (t+1 <= d && heap[t+1] < heap[t]) t++;
        if (heap[t] < heap[x]) {
            swap(heap[x], heap[t]);
            x = t;
            t = 2*x;
        } else break;
    }
}

只能在末尾插入元素x，插入后需要向上调整：

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

可以将末尾元素覆盖开头元素，实现删除堆顶元素，覆盖后需要向下调整：

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

注解：

(1)在大顶堆中，如果某个结点的值变大，则需要向上调整，如果某个结点的值变小，则需要向下调整，代码中所有的小于号要改成大于号，插入元素和删除堆顶操作不变。

---