二叉堆

堆的种类有很多这里我们讨论的时最大堆和最小堆

堆的结构

严格来说,堆也有不同种类。这是一种叫做二叉堆的数据结构,堆就是下图这样的二叉树。

最小堆的性质是儿子的值一定不小于父亲的值。而最大堆的性质则于其相反儿子的值一定更不大于父亲的值。
除此之外,树的节点时按从上到下、从左到右的顺序紧凑排列的。


如上图所示,在向堆中插入数值时,首先在堆的末尾插入该数值,然后不断向上提升直到没有大小颠倒为止。


如上图所示,从队中删除最小值时,首先把堆的最后一个节点的数值复制到根节点上,并且删除最后一个结点。然后不断向下
交换直到没有大小颠倒为止。在向下交换的过程中,如果有两个儿子,那么选择数值较小的儿子(如果儿子比自己小的话)进行交换。

堆的操作的复杂度

堆的两种操作所花的时间都和数的深度成正比。因此,如果一共有$n$个元素,那么每个操作就可以在$O(log_n)$的时间内完成。

堆的实现

注意:

  • 左儿子的编号是自己的编号 $×2+1$
  • 右儿子的编号是自己的编号 $×2+2$
const int N = 10000;
int heap[N], sz;

void push(int x) {
    //自己节点的编号
    int i = sz ++;
    
    while(i > 0) {
        // 父亲结点的编号
        int p = (i = 1) >> 2;

        //如果已经没有大小颠倒则退出
        if (heap[p] <= x) break;

        //父亲节点的数值放下来,而把自己提上去
        heap[i] = heap[p];
        i = p;
    }

    heap[i] = x;
}

int pop() {

    //最小值

    int ret = heap[0];

    //要提到根的数值
    int x = heap[--sz];

    //从根开始向下交换
    int i = 0;
    while ((i << 2) + 1 < sz) {
        //比较儿子的值
        int a = i * 2 + 1, b = i * 2 + 2;
        if (b < sz && heap[b] < heap[a]) a = b;

        //如果已经没有大小颠倒则退出
        if (heap[a] >= x) break;

        //把儿子的数值提上来
        heap[i] = heap[a];
        i = a;
    }

    heap[i] = x;

    return ret;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!