本文参考了Python的官方文档，主要是对常用方法进行分析，并对注意事项进行记录
heapq - 堆队列算法
这是python自带的库函数，实际上是最小堆，使用列表实现，堆顶元素为列表的第一个元素（最小元素）
从零开始计数，对于所有的 k ，都有 heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2]。 为了便于比较，不存在的元素被认为是无限大。 最小的元素总是在根结点：heap[0]
函数
heap = []
heapq.heappush(heap, item)- 将
item的值加入heap中，保持堆的不变性。
- 将
heapq.heappop(heap)- 弹出并返回
heap的最小的元素，保持堆的不变性。如果堆为空，抛出IndexError。 - 使用
heap[0]，可以只访问最小的元素而不弹出它。
- 弹出并返回
heapq.heappushpop(heap, item)- 这个函数是先推入再弹出
- 将
item放入堆中，然后弹出并返回heap的最小元素。 - 保证堆大小不变
- 该组合操作比先调用
heappush()再调用heappop()运行起来更有效率。
heapq.heapreplace(heap, item)- 这个函数是先弹出再推入，返回的值可能会比添加的 item 更大
- 弹出并返回
heap中最小的一项，同时推入新的item。 堆的大小不变。 如果堆为空则引发 IndexError。 - 比 heappop() 加 heappush() 更高效，并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item。
heapq.heapify(x)- 将 list
x转换成堆，原地，线性时间内。
- 将 list
heapq.nlargest(n, iterable, key=None)- 从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。
heapq.nsmallest(n, iterable, key=None)- 从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。
Leetcode 215
数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if k > len(nums):
raise Exception("Error")
L = []
for i in range(k):
heapq.heappush(L, nums[i])
for i in range(k, len(nums)):
if L[0] < nums[i]:
heapq.heappushpop(L, nums[i])
return L[0]
