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

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

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

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

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

给出一段上浮的示例代码:(和线段树一样,这里通常采用一个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;
}

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