二叉堆

简介 #

二叉堆（Binary Heap）是一种基于完全二叉树的数据结构.

小根堆：任意节点 $≥$ 其父节点，根节点最小.
大根堆：任意节点 $≤$ 其父节点，根节点最大.

本篇以小根堆为例，介绍二叉堆的实现方式.

构造 #

按照从上到下，从左到右的顺序给节点编号.

该二叉堆具有以下性质：

$1$ 号节点是根节点.
$u$ 号的父节点为 $\frac{u}{2}$（向下取整）.
$u$ 号的左子节点为 $2u$，右子节点为 $2u+1$.
二叉堆的任意一条支路都按照升序排序.

使用数组保存二叉堆.

int t[], n;
// t[u] : u 号节点的值
// n : 节点总数

插入 #

如何往小根堆中插入元素 $2$？

在堆底新建节点，值为 $2$；
对新节点所在支路进行排序.重复执行以下步骤：
- 若新节点 $<$ 其父节点，则交换它们的位置，否则跳出循环.

时间复杂度为 $O(n\log{n})$.

void push(int val) { // 插入元素 val
    t[++ n] = val; // 新建节点
    for(int u = n; u != 1; u /= 2) {
        if(t[u] < t[u / 2]) swap(t[u], t[u / 2]);
        else break;
    }
}

移除 #

将小根堆的根节点移除，如何调整使其仍为小根堆？

把堆底最后一个元素移到根节点；
从根节点 $u=1$ 开始，重复执行以下步骤：

比较 $u$ 的两个子节点，取最小的一个，记为 $v$；
若 $t[u]>t[v]$，交换节点 $u$ 和 $v$ 的位置，并使 $u=v$，否则跳出循环.

void pop() { // 移除根节点
    t[1] = t[n --];
    for(int u = 1; 2 * u <= n; ) {
        int v = 2 * u;
        if(v + 1 <= n && t[v + 1] < t[v]) v ++; // 取最小的子节点
        if(t[u] > t[v]) swap(t[u], t[v]), u = v;
        else break;
    }
}

模板 #

int t[], n;

void push(int val) {
    t[++ n] = val;
    for(int u = n; u != 1; u /= 2) {
        if(t[u] < t[u / 2]) swap(t[u], t[u / 2]);
        else break;
    }
}

void pop() {
    t[1] = t[n --];
    for(int u = 1; 2 * u <= n; ) {
        int v = 2 * u;
        if(v + 1 <= n && t[v + 1] < t[v]) v ++;
        if(t[u] > t[v]) swap(t[u], t[v]), u = v;
        else break;
    }
}