二叉堆
堆的种类有很多这里我们讨论的时最大堆和最小堆
堆的结构
严格来说,堆也有不同种类。这是一种叫做二叉堆的数据结构,堆就是下图这样的二叉树。
最小堆的性质是儿子的值一定不小于父亲的值。而最大堆的性质则于其相反儿子的值一定更不大于父亲的值。
除此之外,树的节点时按从上到下、从左到右的顺序紧凑排列的。
如上图所示,在向堆中插入数值时,首先在堆的末尾插入该数值,然后不断向上提升直到没有大小颠倒为止。
如上图所示,从队中删除最小值时,首先把堆的最后一个节点的数值复制到根节点上,并且删除最后一个结点。然后不断向下
交换直到没有大小颠倒为止。在向下交换的过程中,如果有两个儿子,那么选择数值较小的儿子(如果儿子比自己小的话)进行交换。
堆的操作的复杂度
堆的两种操作所花的时间都和数的深度成正比。因此,如果一共有$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 协议 ,转载请注明出处!