# 数据结构与算法：大小根堆和快速排序 解决TopK问题

• 大小根堆
• 求最小前k个元素
• 代码示例
• 求最大的前k个元素
• 代码示例
• 统计重复次数最少的k个元素
• 快排分割求TopK

``````#include
#include
#include
#include

using namespace std;

int main(void)
{
vector<int> nums;
srand(time(NULL));
for (int i = 0; i < 1000; ++i)
{
nums.push_back(rand() % 10000 + 1);
}

// 求nums中值最小的前5个元素
priority_queue<int> maxheap;
int k = 5;

// 前k个构建一个大根堆
for (int i = 0; i < k; ++i)
{
maxheap.push(nums[i]);
}

// 遍历剩余元素
for (int i = k; i < nums.size(); ++i)
{
if (maxheap.top() > nums[i])
{
maxheap.pop();
maxheap.push(nums[i]);
}
}

// 输出结果
while (!maxheap.empty())
{
cout << maxheap.top() << " ";
maxheap.pop();
}
cout << endl;

return 0;
}
``````

``````#include
#include
#include
#include
using namespace std;

int main(void)
{
vector<int> nums;
srand(time(NULL));
for (int i = 0; i < 1000; ++i)
{
nums.push_back(rand() % 10000 + 1);
}

// 求nums中值最大的前5个元素
priority_queue<int> minheap;
int k = 5;

// 前k个构建一个大根堆
for (int i = 0; i < k; ++i)
{
minheap.push(nums[i]);
}

// 遍历剩余元素
for (int i = k; i < nums.size(); ++i)
{
if (minheap.top() < nums[i])
{
minheap.pop();
minheap.push(nums[i]);
}
}
// 输出结果
while (!minheap.empty())
{
cout << minheap.top() << " ";
minheap.pop();
}
cout << endl;

return 0;
}
``````

``````#include
#include
#include
#include
#include
#include
using namespace std;

int main(void)
{
vector<int> nums;
srand(time(NULL));
for (int i = 0; i < 1000; ++i)
{
nums.push_back(rand() % 10000 + 1);
}

int k = 3;
// 统计重复次数最小的前3个数字
unordered_map<int, int> map;
for (auto key : nums)
{
map[key]++;
}

// 放入大根堆时，需要放key-value键值对
using Type = pair<int, int>;
using Cmp = function<bool(Type&, Type&)>;
priority_queue<Type, vector<Type>, Cmp> maxheap(
[](Type& a, Type& b)->bool {
return a.second < b.second;
}
);

auto it = map.begin();
for (int i = 0; i < k; ++i, ++it)
{
maxheap.push(*it);
}

for (; it != map.end(); ++it)
{
if (maxheap.top().second > it->second)
{
maxheap.pop();
maxheap.push(*it);
}
}

while (!maxheap.empty())
{
cout << "key: " << maxheap.top().first
<< " cnt: " << maxheap.top().second << endl;
maxheap.pop();
}

return 0;
}
``````

``````#include
#include
#include
#include
#include
#include
using namespace std;

int main(void)
{
vector<int> nums;
srand(time(NULL));
for (int i = 0; i < 1000; ++i)
{
nums.push_back(rand() % 1000 + 1);
}

// 统计重复次数最大的前3个数字
int k = 3;
unordered_map<int, int> map;
for (auto key : nums)
{
map[key]++;
}

// 放入大根堆时，需要放key-value键值对
using Type = pair<int, int>;
using Cmp = function<bool(Type&, Type&)>;
priority_queue<Type, vector<Type>, Cmp> minheap(
[](Type& a, Type& b)->bool {
return a.second > b.second;
}
);

auto it = map.begin();
for (int i = 0; i < k; ++i, ++it)
{
minheap.push(*it);
}

for (; it != map.end(); ++it)
{
if (minheap.top().second < it->second)
{
minheap.pop();
minheap.push(*it);
}
}

while (!minheap.empty())
{
cout << "key: " << minheap.top().first
<< " cnt: " << minheap.top().second << endl;
minheap.pop();
}
return 0;
}
``````

``````#include
#include

using namespace std;

// 分割函数
int Partition(int* nums, int left, int right)
{
int key = nums[left];

while (left < right)
{
while (left < right && nums[right] > key)
right--;

if (left < right)
{
nums[left] = nums[right];
left++;
}

while (left < right && nums[left] < key)
left++;

if (left < right)
{
nums[right] = nums[left];
right--;
}
}

nums[left] = key;
return left;
}

// 求Topk函数
void selectTopK(int* nums, int left, int right, int k)
{
int pos = Partition(nums, left, right);
if (pos == k - 1)
{
return;
}
else if (pos > k - 1)
{
selectTopK(nums, left, pos - 1, k);
}
else
{
selectTopK(nums, pos + 1, right, k);
}
}

void Show(int* nums, int size)
{
for (int i = 0; i < size; ++i)
{
cout << nums[i] << " ";
}
cout << endl;
}

int main(void)
{
int nums[] = { 64, 45, 52, 80, 66, 68, 0, 2, 18, 75 };
int size = sizeof(nums) / sizeof(nums[0]);
Show(nums, size);

// 求值最小的前三个元素
int k = 3;
selectTopK(nums, 0, size - 1, k);
Show(nums, k);
return 0;
}
``````

(0)