14.二叉堆
二叉堆
堆(Heap)是一类数据结构,它们拥有树状结构,且能够保证父节点比子节点大(或小)。当根节点保存堆中最大值时,称为大根堆;反之,则称为小根堆。
二叉堆(Binary Heap)是最简单、常用的堆,是一棵符合堆的性质的完全二叉树。它可以实现 O(logn) 地插入或删除某个值,并且 O(1) 地查询最大(或最小)值。

img
作为一棵完全二叉树,二叉堆完全可以用一个1-index的数组来存储,对于节点p
,p*2
即为左儿子,p*2+1
即为右节点。同时,用size
记录当前二叉堆中节点的个数。
现在我们考虑如何保证二叉堆的性质不被破坏。实际上,对于一个破坏堆性质的节点,我们可以使其上浮或下沉,因为最差也不过是上浮到顶或是下沉到底,所以只需要 O(logn) 的时间就可以使其不再破坏性质。稍后我们会看到,插入和删除都只需要上浮/下沉一个节点。
上浮
很简单,不断与父节点比较,如果比父节点大(以大根堆为例,下同)就与之交换,直到不大于父节点或成为根节点为止。
1 | void swim(int n) |
下沉
类似地,不断与较大的子节点比较,如果比它小就与之交换,直到不小于任何子节点或成为叶子节点为止。之所以要与较大的子节点比较,是为了保证交换上来的节点比两个子节点都大。
1 | int son(int n) // 找到需要交换的那个子节点 |
插入
直接在尾部插入值,然后上浮即可。
1 | void insert(int x) |
删除
可以将根节点与最后一个节点交换,使size
减1,然后再下沉。
1 | void pop() |
查询
直接返回根节点即可。
1 | int top() |
建立
可以从一个数组 O(n)地建立堆,只需复制过来然后从底部到顶部依次下沉即可。实际上因为叶子节点不需要下沉,所以可以从 n/2 处开始遍历。
1 | void build(int A[], int n) // 从一个(这里是0-index的)数组O(n)地建立二叉堆 |
使用手写的二叉堆,会比STL
提供的priority_queue
快一些。此外,了解其原理也有助于理解一些更高级的数据结构。接下来提供一个可以方便地在小根堆和大根堆间切换的模板(利用了宏定义):
1 | namespace heap |
0.AcWing 145. 超市
贪心策略:对于 t tt 天,我们需要在保证不卖出过期商品的前提下,卖出利润前 t tt 大的商品。
因此我们可以把商品按照过期时间排序,然后建立一个小根堆,对于每一个数而言,如果说它的过期时间大于当前小根堆的个数,那么我们可以直接将这个货物的价值加入进来,如果说当前过期时间等于这个小根堆堆内的个数,那么我们就需要对比一下,如果说这个货物的价值,是高于小根堆的堆顶的话,那么我们就将小根堆堆顶弹出,然后push我们这个新货物,因为新货物明显是更加优于堆顶的老货物的,因为每次都选择最优的选项,保证了算法的正确性。

itingyu 微信打赏
微信打赏
Related Issues not found
Please contact @itingyu to initialize the comment