347. [✔][M]前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

---

题解：

手写heap

// @lc code=start
function topKFrequent(nums: number[], k: number): number[] {
    class Heap {
        data: any[];
        comp: (a: number, b: number) => boolean;
        constructor(data: any[] = [], comp = (a: number, b: number) => a < b) {
            this.data = data;
            this.comp = comp;
            this.heapify();
        }

        get size() {
            return this.data.length;
        }

        heapify() {
            for (let i = Math.floor(this.size / 2 - 1); i >= 0; i--) {
                this.down(i);
            }
        }

        down(index: number) {
            let lastIndex = this.size - 1;

            while (true) {
                let findIndex = index;
                let leftIndex = findIndex * 2 + 1;
                let rightIndex = findIndex * 2 + 2;

                if (leftIndex <= lastIndex && this.comp(this.data[findIndex], this.data[leftIndex])) {
                    findIndex = leftIndex;
                }

                if (rightIndex <= lastIndex && this.comp(this.data[findIndex], this.data[rightIndex])) {
                    findIndex = rightIndex;
                }

                if (findIndex !== index) {
                    this.swap(index, findIndex);
                    index = findIndex;
                } else {
                    break;
                }
            }
        }

        up(index: number) {
            while (index > 0) {
                let parentIndex = (index - 1) >> 1;
                if (this.comp(index, parentIndex)) {
                    this.swap(index, parentIndex);
                    index = parentIndex;
                } else {
                    break;
                }
            }
        }

        push(value: any) {
            this.data.push(value);
            this.up(this.size - 1);
        }

        pop() {
            if (this.size === 0) {
                return null;
            }
            this.swap(0, this.size - 1);
            let res = this.data.pop();
            this.down(0);
            return res;
        }

        swap(i, j) {
            [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
        }
    }

    let map = new Map();//记录value出现的次数

    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) {
            map.set(nums[i], 1);
        } else {
            map.set(nums[i], map.get(nums[i]) + 1);
        }
    }

    let data = Array.from(map.entries());

    let heap = new Heap(data, (a, b) => a[1] > b[1]);

    while (heap.size > k) {
        heap.pop();
    }

    let res: number[] = new Array(k);

    for (let i = k - 1; i >= 0; i--) {
        res[i] = heap.pop()![0];
    }

    return res;
};
// @lc code=end