# 题目

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

示例 1:

示例 2:

提示：

347. 前 K 个高频元素 - 力扣（LeetCode）

# 分析

这道题目主要涉及到如下三块内容：

首先统计元素出现的频率，这一类的问题可以使用 map 来进行统计。

然后是对频率进行排序，这里我们可以使用一种容器适配器就是优先级队列。

什么是优先级队列呢？

优先级队列（Priority Queue）是一种特殊类型的队列，其中每个元素都有一个与之关联的优先级。具有较高优先级的元素在队列中排在较低优先级元素的前面。

优先级队列的特点是可以确保在插入或删除元素时，始终能够以适当的顺序处理具有最高优先级的元素。

通常，优先级队列使用堆（Heap）数据结构来实现，也可通过二叉搜索树等其他结构来实现。

优先级队列的常见操作包括插入（Insertion）、删除最大 / 最小元素（Delete Max/Min），以及查找最大 / 最小元素（Find Max/Min）等。这些操作的复杂度通常为 O (log n)，其中 n 是队列中的元素数量。

优先级队列在很多应用中都有广泛的使用，如调度算法、图算法、模拟系统等，它能够高效地对元素进行排序和筛选。

什么是堆？

在数据结构中，堆（Heap）是一种特殊的树形数据结构，通常指的是二叉堆（Binary Heap），也称为最小堆（Min Heap）或最大堆（Max Heap）。

堆具有以下特性：

最小堆的特点是根节点的值最小，任意节点的值都小于或等于其子节点的值。最大堆的特点则是根节点的值最大，任意节点的值都大于或等于其子节点的值。

	// 时间复杂度: O (nlogk)
	// 空间复杂度: O (n)
	class Solution {
	public:
	// 小顶堆
	class mycomparison {
	public:
	bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
	return lhs.second > rhs.second;
	}
	};
	vector<int> topKFrequent(vector<int>& nums, int k) {
	// 要统计元素出现频率
	unordered_map<int, int> map; //map<nums [i], 对应出现的次数 >
	for (int i = 0; i < nums.size(); i++) {
	map[nums[i]]++;
	}

	// 对频率排序
	// 定义一个小顶堆，大小为 k
	priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

	// 用固定大小为 k 的小顶堆，扫面所有频率的数值
	for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
	pri_que.push(*it);
	if (pri_que.size() > k) { // 如果堆的大小大于了 K，则队列弹出，保证堆的大小一直为 k
	pri_que.pop();
	}
	}

	// 找出前 K 个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
	vector<int> result(k);
	for (int i = k - 1; i >= 0; i--) {
	result[i] = pri_que.top().first;
	pri_que.pop();
	}
	return result;

	}
	};

堆栈堆