type
status
password
date
slug
summary
category
URL
tags
icon
今天介绍一个 Python 的库
heapq，默认的堆结构是小顶堆。在很多时候使用优先队列解决问题的时候会用到。在后面和大家一起 LeetCode 刷题过程中会用到！一、构造堆 & 获取最小值
方法一：创建空列表，然后手动加入元素
方法二：初始化 list，然后转为堆结构
方法 | 描述 |
heapq.heapify(x) | 将list x 转换成堆，原地，线性时间内。 |
heapq.heappush(heap,item) | 将 item 的值加入 heap 中，保持堆的不变性。 |
heapq.heappop(heap) | 弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。使用 heap[0] ，可以只访问最小的元素而不弹出它。 |
heapq.heappushpop(heap, item) | 将 item 放入堆中，然后弹出并返回 heap 的最小元素。 |
heapq.heapreplace(heap, item) | 弹出并返回 heap 中最小的一项，然后推入新的 item。 |
heapq.nlargest(n,iterable,key=None) | 从数据集中返回前 n 个最大元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，对每个元素中提取比较键 (例如 key=str.lower)。 等价: sorted(iterable, key=key, reverse=True)[:n]。 |
heapq.n,iterable,key=None) | 从数据集中返回前 n 个最小元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，对每个元素中提取比较键 (例 key=str.lower)。 等价于: sorted(iterable, key=key)[:n]。 |
二、获取最大值
这里没有直接构造大顶堆的方法，可以使用一个很巧妙的思路进行解决。首先我们用上述方法一进行构造堆结构，注意要在每一个元素增加一个负号（-）：
三、获取最小值和最大值的范围
获取堆中最大或最小的范围值。使用
heapq.nlargest() 或heapq.nsmallest() 函数进行求得：四、操作字典
五、数组（如果元素是元组，那么首先比较第1个元素，其次比较第2个元素，依次类推。）
包含自定义类的最小堆问题
需要重载自定义类中的比较函数，如
__lt__(self, other)函数 | __lt__(self, other) | __le__(self,other) | __gt__(self, other) | __ge__(self, other) |
含义 | < | ≤ | > | ≥ |
示例 | return self.weight<other.weight | ㅤ | ㅤ | ㅤ |
703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。请实现 KthLargest 类：
KthLargest(int k, int[] nums)使用整数 k 和整数流 nums 初始化对象。
int add(int val)将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8]解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); // 4, 5, 8 kthLargest.add(3); // return 4 小顶堆 4, 5, 8 kthLargest.add(5); // return 5 5, 5, 8 kthLargest.add(10); // return 5 5, 8, 10 kthLargest.add(9); // return 8 8, 10, 9 kthLargest.add(4); // return 8 8, 10, 9