大顶堆与小顶堆应用---寻找前k小数

大顶堆与小顶堆应用---寻找前k小数

 vector<int>  getLeastNumber(vector<int>&  arr,int k){

 vector<int> vec(k,);

 if(==k)

 return vec;

 priority_queue<int> q;

 for(int i = ;i < k;i++){

 q.push(arr[i]);

 }

 for(int i = k;i <(int)arr.size();i++){

 if(q.top()>arr[i]){

 q.pop();

 q.push(arr[i]);

 }

 }

 for(int i = ;i < k;i++){

 vec[i] = q.top();

 q.pop();

 }

 return vec;

 }

我们用一个大根堆实时维护数组的前 kk 小值。

首先将前 kk 个数插入大根堆中，随后从第 k+1k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数d出，再插入当前遍历到的数。

最后将大根堆里的数存入数组返回即可。

在下面的代码中，由于 C++ 语言中的堆（即优先队列）为大根堆，我们可以这么做。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。

商业转载请联系作者获得授权，非商业转载请注明出处。

//定义方式

priority-queue<int> p;//最大值优先，大顶堆的简写方式
priority-queue<int,vector<int>,greater<int> > q1;//最小值优先，小顶堆
priority-queue< int,vector<int>,less<int> > q2;//最大值优先，大顶堆

//第一个参数--数据类型，第二个参数--容器类型，第三个参数--比较函数
}

{
//结构体的优先级比较方式

struct node{
string name;
int price;
friend bool operator < (node a,node b)
{
return a.price < b.price;
}
//相当于less,这是大顶堆，反之是小顶堆，最大值优先
}stu;

priority-queue<node> q;

//常用 *** 作
q.push(x);
q.pop();
q.top();
q.size();
q.empty();
}

{
//举例
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

struct node
{
friend bool operator< (node n1,node n2)
{
return (n1.priority < n2.priority);
}

int priority;
int value;
};

int main()
{
const int len = 5;
int i;
int a[len] = {3,5,9,6,2};

//从大到小输出
priority-queue<int> q1;
for (int i = 0;i < len;i++)
q1.push[a[i]);

for (int i = 0;i < len;i++）
{
cout << q1.top() <<　" ";
q1.pop();
}
cout << endl;

//从小到大输出
priority-queue<int,vector<int>,greater<int> > q2;
for (int i = 0;i < len;i++)
q2.push(a[i]);

for (int i = 0;i < len;i++)
{
cout << q2.top() << " ";
q2.pop();
}
cout << endl;

//按优先级输出
priority-queue<node> qn;
node b[len];
b[0].priority = 6;b[0].value = 1;
b[1].priority = 9;b[1].value = 5;
b[2].priority = 2;b[2].value = 3;
b[3].priority = 8;b[3].value = 2;
b[4].priority = 1;b[4].value = 4;

for (int i = 0;i < len;i++)
qn.push(b[i]);

cout << "优先级" << '\t' << "值" << endl;
for (int i = 0;i < len;i++)
{
cout << qn.top().priority << '\t' << qn.top().value << endl;
qn.pop();
}
cout << endl;

}
}