二叉堆的实现

我一直以为实现一个二叉堆是很困难的事情，还以为会用到树翻转这种经典梗问题，结果自己实现了一下，发现非常简单，甚至比传统的几个排序：快速排序、归并排序还要简单、好写的多。

堆这种数据结构，目的是实现一种优先队列。它可以在比较好的复杂度下实现优先队列的各项操作。

二叉堆的实现，典型的使用的是线性存储，这一点和线段树比较像（原谅我这几天写了太多的线段树，脑子都写迷糊了）。

构建方式采用的是上浮法。通过让每一个节点与父节点比较，如果节点比他的父节点更加优先，就将其递归的上浮，直到根节点。这样可以对每一个结构进行遍历。

从此处我们可以看出，需要注意的是，二叉堆并不是一颗搜索树。它只能保证顶端节点是最优先的节点，而不能对其他任何节点给出判断。因此二叉堆是不能用于静态查询的。通常的静态应用会采用二叉堆进行一次排序。

给出一段上浮的示例代码：（和线段树一样，这里通常采用一个1-base的数组）

1
2
3
4
5
6
7
8
9

void siftup(int node) {
    if (node == 1 || node == 0)
        return;
    if (storage[node] < storage[node >> 1]) {
        swap(storage[node], storage[node >> 1]);
        siftup(nodec >> 1);
    }
    return;
}

堆可以比较高效率的实现优先队列的入队与出队。

对于一个入队过程，只需要将元素放到最后一位，然后对其执行上浮即可。这一点和构建一个堆是等价的。

对于一个出队过程，显然，我们已经知道出队的元素在堆的顶端。我们抽走队列的头节点，然后把队列的尾部放到头节点的位置。此后我们执行一个下沉的操作。对一个节点的两个子节点，对各个子树递归的下沉。需要注意的是，两颗子树都要进行下沉的判断工作，因为如前文所述，堆只有头部是满足最优先，而对其他的数据给不出任何判断。

给出一段下沉的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

void heapify(int node, int treesize) {
    if (node >= treesize)
        return;
    if (node << 1 <= treesize && storage[node] > storage[node << 1]) {
        swap(storage[node], storage[node << 1]);
        heapify(node << 1, treesize);
    }
    if ((node << 1 | 1) <= treesize && storage[node] > storage[node << 1 | 1]) {
        swap(storage[node], storage[node << 1 | 1]);
        heapify(node << 1 | 1, treesize);
    }
    return;
}

到此为止，这个过程非常简单。甚至来讲，我们把“把队列的尾部放到头节点的位置”换成“把队列的尾部和头节点交换”，我们就实现了一个原地的堆排序。这个排序方向和堆的优先方向是相反的。