堆

介绍

堆是一颗完全二叉树，树中每个节点的值的小于等于左右孩子的节点的值（小根堆）。

存储

堆使用一维数组heap[]搭建。节点从1开始，对于任意一个节点x,他的左孩子为2x,右孩子为2x+1。

操作

up(x)

向上调整x的位置，使之处于正确的位置。

down(x)

向下调整x的位置，使之处于正确的位置。

建堆

只要从最后一个非叶节点倒着开始即可。

for(int i = n / 2; i > 0; i--){
    down(i);
}

插入一个数

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

求集合中最小的值

heap[1]

删除最小值

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

删除任意一个元素

heap[k] = heap[size];
size--;
down(k);
up(k);

修改任意一个元素

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