首先认识堆：
堆的示意图
1、认识python3中关于堆的函数
1）heapq.heapify可以原地把一个list调整成堆[小顶堆] 而 heapq.nlargest 会调成大顶堆
2）heapq.heappop可以弹出堆顶，并重新调整
3）heapq.heappush可以新增元素到堆中，不会调整
4）heapq.heapreplace可以替换堆顶元素，并调整下
5）为了维持为K的大小，初始化的时候可能需要删减，后面需要做处理就是如果不满K个就新增，否则做替换；
6）heapq其实是对一个list做原地的处理，第一个元素就是最小的，直接返回就是最小的值
1、最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
关键点
1、取负值，建最小堆，实质上是最小的K个数（堆顶取正值后最大）
2、遍历剩下的元素，维护这个最小堆，关键数判断值与堆顶元素的关系，如果值大于堆顶元素，要加入堆
代码如下：
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k == 0:
return list()
tmp=[-x for x in arr[:k]]
heapq.heapify(tmp)
#最小堆，最顶最小，实质上是最小的k个数
for i in range(k, len(arr)):
if tmp[0] < -arr[i]:
heapq.heappop(tmp)
heapq.heappush(tmp, -arr[i])
return [-x for x in tmp]
？？？利用最大堆如何实现？？？
2、数据流中第K大元素
设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。
关键点
1、使用最小堆，得到第K个大的数，构建k个值的最小堆
2、判断值于堆顶元素的关系，如果值大于堆顶元素，插入并重新调整，返回堆顶元素
代码如下：
from heapq import *
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.nums = nums
heapify(self.nums)
while len(self.nums)>self.k: #cut heap to size:k
heappop(self.nums)
def add(self, val):
"""
:type val: int
:rtype: int
"""
if len(self.nums) < self.k:
heappush(self.nums, val)
heapify(self.nums) #cation
else:
top = float('-inf')
if len(self.nums) > 0:
top = self.nums[0]
if top < val:
heapreplace(self.nums, val)
#替换堆顶元素，病调整下
return self.nums[0]
参考资料：
1、python实现最大堆，最小堆和堆排序https://blog.csdn.net/qq_40587575/article/details/89290135#0.%E4%BB%80%E4%B9%88%E6%98%AF%E5%A0%86
2、Python的heapq的文档
网友评论