[数据结构与算法]python heappush heappop的用法+leetcode347

1.heappush(heap,item)建立大、小根堆

heapq.heappush()是往堆中添加新值，此时自动建立了小根堆

不能直接建立大跟堆，所以每次push时给元素加一个负号（即取相反数），此时最小值变最大值，反之亦然，那么实际上的最大值就可以处于堆顶了，返回时再取负即可。

2.heapq.heappop()从堆中弹出并返回最小的值

普通list（即并没有进行heapify等操作的list），对他进行heappop操作并不会弹出list中最小的值，而是弹出第一个值。

对于小跟堆，会依次弹出最小的值。

所以针对最小 top k 问题用最大堆，求最大 top k 问题用最小堆
比如leetcode347中，求最大top k问题，先求出各个数字出现的频率，再建立一个小跟堆，每次把频率最小的值弹出来，最后剩下一个k大小的list，就是要求的前k个高频元素了。

# 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
# 统计元素出现的频率，这一类的问题可以使用map来进行统计。
# 然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列
# 优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
# 而且优先级队列内部元素是自动依照元素的权值排列。heapq这个模块提供了堆队列算法的实现，也称为优先队列算法。
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map_={}
        for i in range(len(nums)):
            map_[nums[i]]=map_.get(nums[i],0)+1
        hashmap=[]
        for key,freq in map_.items():
            heapq.heappush(hashmap,(freq,key))
            if len(hashmap)>k:
                heapq.heappop(hashmap)
        re=[0]*k
        for i in range(k-1,-1,-1):
            re[i]=heapq.heappop(hashmap)[1]
        return re

map_[nums[i]]=map_.get(nums[i],0)+1
#get的赋值语句，目的是新建字典键值对

等价于

map_[nums[i]]=0
map_[nums[i]]+=1