题目

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

来源：力扣（LeetCode）

Python解法

二叉堆与优先队列

这道题用到了二叉堆与优先队列的相关知识点。

二叉树本质是一种完全二叉树，它分为最大堆和最小堆。最大堆的任何一个父节点，都大于等于它的左子节点或右子节点的值。最小堆的任何一个父节点，都小于等于它的左子节点或右子节点的值。二叉堆的根节点叫作堆顶，最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素。

队列的特点是先进先出（FIFO）。而优先队列不再遵循先入先出的规则，而是分为两类：最大优先队列和最小优先队列。最大优先队列是无论入队顺序如何，都是当前最大的元素优先出队。最小优先队列是无论入队顺序如何，都是当前最小的元素优先出队。

因此，我们可以结合以上两部分知识来解决这道题。具体思路如下：

• 根据给定数组计算每个元素的个数并将其转换成列表的形式 stat，列表 stat 中的元素形式为 (某一种元素, 元素个数)；
• 因为最小堆是一种完全二叉树，我们假设完全二叉树是从索引 1 开始计算的，因此对于索引 i，它的左子节点索引是 2i，右子节点索引是 2i+1；
• 创建最小堆 heap，在最开始插入一个占位节点 (0, 0)，此时最小堆堆顶索引与数组 heap 索引为 1 的位置相同；
• 读取 stat 中前 k 个元素，将其逐个放入数组 heap 中并利用上浮方法进行排序，最终二叉堆的规模为 k+1，多出来的1 为占位节点；
• 依次读取 stat 中除前 k 个元素外剩下的元素，并判断该元素对应的元素个数是否大于二叉堆的堆顶，即是否 heap[1]；
• 如果大于，说明相比于 heap[1] 该元素更满足要求，将堆顶用该元素替换，然后将该元素逐渐下沉到它应在的位置；
• 最后，排除占位节点输出 heap[1:] 即为所求结果。

代码如下：

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    def sift_down(arr, root, k):
        """下沉log(k),如果新的根节点>子节点就一直下沉"""
        val = arr[root] # 用类似插入排序的赋值交换
        while root<<1 < k:
            child = root << 1
            # 选取左右孩子中小的与父节点交换
            if child|1 < k and arr[child|1][1] < arr[child][1]:
                child |= 1
            # 如果子节点<新节点,交换,如果已经有序break
            if arr[child][1] < val[1]:
                arr[root] = arr[child]
                root = child
            else:
                break
        arr[root] = val

    def sift_up(arr, child):
        """上浮log(k),如果新加入的节点<父节点就一直上浮"""
        val = arr[child]
        while child>>1 > 0 and val[1] < arr[child>>1][1]:
            arr[child] = arr[child>>1]
            child >>= 1
        arr[child] = val

    stat = collections.Counter(nums)
    stat = list(stat.items())
    heap = [(0,0)]

    # 构建规模为k+1的堆,新元素加入堆尾,上浮
    for i in range(k):
        heap.append(stat[i])
        sift_up(heap, len(heap)-1) 
    # 维护规模为k+1的堆,如果新元素大于堆顶,入堆,并下沉
    for i in range(k, len(stat)):
        if stat[i][1] > heap[1][1]:
            heap[1] = stat[i]
            sift_down(heap, 1, k+1) 
    return [item[0] for item in heap[1:]]