我一直以为实现一个二叉堆是很困难的事情,还以为会用到树翻转这种经典梗问题,结果自己实现了一下,发现非常简单,甚至比传统的几个排序:快速排序、归并排序还要简单、好写的多。
堆这种数据结构,目的是实现一种优先队列。它可以在比较好的复杂度下实现优先队列的各项操作。
二叉堆的实现,典型的使用的是线性存储,这一点和线段树比较像(原谅我这几天写了太多的线段树,脑子都写迷糊了)。
构建方式采用的是上浮法。通过让每一个节点与父节点比较,如果节点比他的父节点更加优先,就将其递归的上浮,直到根节点。这样可以对每一个结构进行遍历。
从此处我们可以看出,需要注意的是,二叉堆并不是一颗搜索树。它只能保证顶端节点是最优先的节点,而不能对其他任何节点给出判断。因此二叉堆是不能用于静态查询的。通常的静态应用会采用二叉堆进行一次排序。
给出一段上浮的示例代码:(和线段树一样,这里通常采用一个1-base的数组)
1 | void siftup(int node) { |
堆可以比较高效率的实现优先队列的入队与出队。
对于一个入队过程,只需要将元素放到最后一位,然后对其执行上浮即可。这一点和构建一个堆是等价的。
对于一个出队过程,显然,我们已经知道出队的元素在堆的顶端。我们抽走队列的头节点,然后把队列的尾部放到头节点的位置。此后我们执行一个下沉的操作。对一个节点的两个子节点,对各个子树递归的下沉。需要注意的是,两颗子树都要进行下沉的判断工作,因为如前文所述,堆只有头部是满足最优先,而对其他的数据给不出任何判断。
给出一段下沉的示例代码:
1 | void heapify(int node, int treesize) { |
到此为止,这个过程非常简单。甚至来讲,我们把“把队列的尾部放到头节点的位置”换成“把队列的尾部和头节点交换”,我们就实现了一个原地的堆排序。这个排序方向和堆的优先方向是相反的。