我一直以为实现一个二叉堆是很困难的事情,还以为会用到树翻转这种经典梗问题,结果自己实现了一下,发现非常简单,甚至比传统的几个排序:快速排序、归并排序还要简单、好写的多。
堆这种数据结构,目的是实现一种优先队列。它可以在比较好的复杂度下实现优先队列的各项操作。
二叉堆的实现,典型的使用的是线性存储,这一点和线段树比较像(原谅我这几天写了太多的线段树,脑子都写迷糊了)。
构建方式采用的是上浮法。通过让每一个节点与父节点比较,如果节点比他的父节点更加优先,就将其递归的上浮,直到根节点。这样可以对每一个结构进行遍历。
从此处我们可以看出,需要注意的是,二叉堆并不是一颗搜索树。它只能保证顶端节点是最优先的节点,而不能对其他任何节点给出判断。因此二叉堆是不能用于静态查询的。通常的静态应用会采用二叉堆进行一次排序。
给出一段上浮的示例代码:(和线段树一样,这里通常采用一个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 ; }
到此为止,这个过程非常简单。甚至来讲,我们把“把队列的尾部放到头节点的位置”换成“把队列的尾部和头节点交换”,我们就实现了一个原地的堆排序。这个排序方向和堆的优先方向是相反的。
Author:
Victrid
Permanent Link:
https://victrid.dev/2020/dui-de-shi-xian/
License:
Copyright (c) 2022 victrid Terms of Use
Ads by Google
Read our privacy policy on how these personalized advertisements are
delivered to you.
For your reading experience, we provide full-text RSS feeds .
Although math formulas cannot be displayed well, the interface can be adjusted as you like
and there are no ads.