Python 优化堆删除操作

博主： admin
发布时间：2021 年 05 月 20 日
519次浏览
1 条评论
1138字数
分类：蓝桥杯

Python 的 heapq 模块提供了优先队列算法，但是 Python 不支持删除堆中某个元素，一种有效的解决方法是把需要删除的元素先保存起来，等到取队首（list[0]）时，先判断队首（list[0]）是不是要删除的元素。

以力扣 [218. 天际线问题](https://leetcode-cn.com/problems/the-skyline-problem/) 为例

```python
import heapq
from collections import defaultdict
class Solution:
    def getSkyline(self, buildings: 'List[List[int]]') -> 'List[List[int]]':
        shoulddel = defaultdict(int)  #用来保存要删除的元素,以实现 Python 中快速删除堆中某个元素
        maxheight = 0
        res = []
        pos = []
        for i in buildings:
            pos.append((i[0],-i[2]))
            pos.append((i[1],i[2]))
        pos.sort()

h = [0]

for i in pos:
            if i[1] < 0:
                heapq.heappush(h,i[1]) #本来是-i[1],但 Python 默认是最小堆，因此是 i[1]
            else:
                shoulddel[i[1]] += 1   #记录要删除的元素
        
            while h and shoulddel[-h[0]] > 0:   #先判断是不是要删除的元素
                shoulddel[-h[0]] -= 1
                heapq.heappop(h)

nowmax = -h[0]
            if nowmax != maxheight:
                res.append([i[0],nowmax])
                maxheight = nowmax
        return res
```

最后修改：2021 年 09 月 09 日 03 : 15 PM

如果觉得我的文章对你有用，请随意赞赏