数据结构与算法：大小根堆和快速排序 解决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)

• 谜语人是什么意思

谜语人，网络流行语，指本来一两句话就能讲明白的事情，非要在其中插进一大堆意义不明对剧情根本没有一点用处的话，就像讲谜语一样。。也指说话故弄玄虚，半、天放不出屁来的人。谜语人滚出哥谭！ 关于谜语人，举个

• 你这是在为难我胖虎是什么意思

为难我胖虎，如字面意思，你不要为难我啊，就是当某些不想做的事情落在头上时可使用的句子。为难我胖虎出处：来源：《哆啦A梦》表情包出自一张表情包，图中胖虎一脸凶神恶煞，并配词“我看，你就是刁难我胖虎”，胖

• 网络语WDM是什么意思

wdm， 饭圈用语，我的妈的意思。wdm，表示震惊，感叹例如：wdm 真的有这样的好事!!网络语WDM是什么意思wdm， 饭圈用语，我的妈的意思。wdm，表示震惊，感叹例如：wdm 真的有这样的好事

2022-12-06
000
• 网络语铲屎官是什么意思

铲屎官，网络流行语，意指给猫、狗铲屎的人类。爱猫爱狗人士将自己比作铲屎官，以表诙谐幽默气氛。多数用来指养猫、养狗者。汪星人与喵星人每次便便完后，只能由人来为其清理便便，久而久之，人就变成铲屎官喽。这是

2022-12-06
000
• 神龛是什么意思

神龛，顾名思义，就是古时候民间用来供奉神像或者是祖宗牌位的阁子。神龛有大有小，一般常见于祠堂之中，是由木头雕刻而成的。古时候的大户人家家里会有专门用来供奉祖先牌位的祠堂，而祠堂里都放置雕刻精美的神龛

2022-12-06
000
• 正史三国谋士真实排行榜

三国谋士正史上没有进行评比，正史中杰出的谋士有荀彧、郭嘉、孔明、庞统、鲁肃周瑜、陆逊、贾诩、程昱、田丰，荀彧是曹魏第一谋臣，不仅谋略过人，而且政略出众，是一个

2022-12-06
000
• 馆陶为什么恨窦漪房

历史上，馆陶是窦漪房的女儿，窦漪房视馆陶如掌上明珠般，馆陶从小被窦漪房呵护着长大，性格娇蛮任性。而且很天真，很容易就听信了别的的馋言。馆陶事事与母亲对着干，馆

2022-12-06
000
• 诸葛瑾的一生是怎样的

诸葛瑾，字子瑜，三国时期吴国重臣。他为人胸怀宽广，温厚诚信，深得孙权的信赖。诸葛瑾年轻时博览群书，后来因中原战乱而避乱江东。在孙权的姊婿曲阿弘咨的推荐下，孙权任命诸葛瑾为中司马。公元219年，诸葛瑾跟

2022-12-06
000
• 黄巾起义领导者是谁

黄巾起义领导者是张角，这场农民战争发生在东汉末年汉灵帝时期，当时东汉政权被宦官和外戚所掌控，朝廷迂腐不堪，争斗不断，不仅国力日渐衰弱，百姓的日子也是苦不堪言，这时候巨鹿人张角发动了黄巾起义，贫苦农民

2022-12-06
000