【Leetcode 347】,前k个高频元素，小根堆的调整

参考题解

题目：给定一个数组，输出 前k个高频元素。
思路：
遍历数组，建立小根堆（小根堆的元素是元组（num,freq），排序规则是每个元素的频率）。
下面使用数组‘heap’，函数’shift_down’,函数‘shift_up’等实现小根堆及其调整（上浮、下沉）。

 def topKFrequent(self, nums: List[int], k: int) -> List[int]:def shift_down(arr,root,k):# 下沉的原因是，新换了堆顶，我们需要为这个堆顶元素找到它在堆中的正确位置# k表示目前堆的有效大小val=arr[root] # root node : <num,freq>while root<<1 <k:child=root<<1if child|1<k and arr[child|1][1]<arr[child][1]:child|=1if arr[child][1]<val[1]:arr[root]=arr[child]root=childelse:breakarr[root]=valdef shift_up(arr,child):# 上浮调整操作，# 上浮原因是，我们在堆的末尾添加了新元素，我们需要为这个新元素找到它在堆中的正确位置val=arr[child]while child>>1 >0 and arr[child>>1][1]>val[1]:arr[child]=arr[child>>1]child>>=1arr[child]=valstat=collections.Counter(nums)# 清点数组nums中的元素个数stat=list(stat.items())heap=[(0,0)] # 用（0，0）做垫底，为了实现在数组中方便找到父子节点之间的联系，如果父节点的索引是root，那么左孩子的索引是root<<1，右孩子的索引是(root<<1)|1。相反地，如果孩子的索引是child，那么父的索引是child>>1for i in range(k):heap.append(stat[i])shift_up(heap,len(heap)-1)for i in range(k,len(stat)):if heap[1][1]<stat[i][1]:heap[1]=stat[i]shift_down(heap,1,k+1)return [item[0] for item in heap[1:]]