堆的基本知识

堆是一个完全二叉树
小根堆：每一个点都是小于等于左右儿子的
大根堆：每一个点都是大于等于左右儿子的

用一维数组存放：x处的左儿子：2x，右儿子：2x + 1
此处下标从1开始 ，若从0开始， 则0的2倍还是0发生冲突

1. 插入一个数

    //size表示堆的大小
    heap[++size] = x; up(size);

1. 求集合当中的最小值

    heap[1] // 小根堆

1. 删除最小值

    //小根堆
    heap[1] = heap[size]; //最后一个点拿到第一个点的位置上
    size --; //干掉最后一个点
    dwon(1); //让1号点下沉，形成新的堆

1. 删除任意一个元素

    heap[k] = heap[size];
    size--;
    down(k);
    up(k);//简化代码down和up都执行一遍

1. 修改任意一个元素为x

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