# C + + TOPK problem

2020-12-06 17:44:58

https://blog.csdn.net/SmartDemo/article/details/107572238

https://blog.csdn.net/wuqingshan2010/article/details/108508676

``````	int K = 5;
std::vector<float> scores;

scores.push_back(0.56);//  Press in elements
scores.push_back(10.56);//  Press in elements
scores.push_back(01.56);//  Press in elements
scores.push_back(02.56);//  Press in elements
scores.push_back(05.56);//  Press in elements
scores.push_back(50.56);//  Press in elements
scores.push_back(30.56);//  Press in elements
std::vector<size_t> idx(scores.size());
//std::iota(idx.begin(), idx.end(), 0);
std::sort(idx.begin(), idx.end(),
[&scores](size_t index_1, size_t index_2) { return scores[index_1] > scores[index_2]; });
//  obtain K value
int k_num = std::min<int>(scores.size(), K);
std::vector<float> scores_K;
int idx_j = 0;
for (int j = 0; j < k_num; ++j) {
idx_j = idx[j];
scores_K.push_back(scores[idx_j]);
}``````

Cannot return index ：

https://blog.csdn.net/doctor_xiong/article/details/81083942

for example ：`arr[] = {9,1,6,2,3,8,3,4,7,0}` The biggest four elements are `6,7,8,9`

Ideas ： Using small piles , First of all, the array of K Elements inserted into the heap , And then from the K Start traversing the array , If the elements in the array are greater than , Heap top element , It's going to be the top element pop, And then the elements in the array push Get in the pile

Implementation code ：

``````#include<iostream>
using namespace std;
#include<queue>
class compare{
public:
bool operator()(int a,int b){
return a > b;
}
};

int* FindTopK(int* arr,int n,int* ret,int m){
compare com;
priority_queue<int,vector<int>,greater<int> > q(arr,arr+m);
int i = m;
for(;i<n;i++){
if(arr[i] > q.top()){
q.pop();
q.push(arr[i]);
}
}
int j = 0;
while(!q.empty()){
ret[j++] = q.top();
q.pop();
}
}

int main(){
int arr[] = {9,4,5,2,5,1,7,3,1,8};
int ret[5];
FindTopK(arr,10,ret,5);
for(int i = 0;i<5;i++)
cout<<ret[i]<<" ";
return 0;
}``````

Reference resources 1：

https://blog.csdn.net/qq_37891889/article/details/88621591

Reference resources 2：

https://blog.csdn.net/weixin_43860854/article/details/108616568

Reference resources 3：

https://blog.csdn.net/propro1314/article/details/43091387

Reference resources ：https://blog.csdn.net/Hairy_Monsters/article/details/79776744

``````/* Case one —— Binary heap C++ Code implementation */
/*
* The code uses STL The implementation of minimum priority queue in , because STL With minimum priority queue in , The bottom layer is a binary heap implementation ,
* So I don't write binary pile anymore . The top element of the minimum priority queue is always the smallest element in the queue , It's the top of the bifurcated reactor .
*/

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

/* because STL The built-in priority queue is the default maximum priority , So I wrote a comparison function , Change it to minimum priority */
struct cmp1 {
bool operator ()(int &a, int &b) {
return a>b;											// Minimum priority
}
};

int main() {
// This is used to test , Input format ： First enter the maximum required K Of the number of K value , Then input the data stream in turn
int K = 0;
cin >> K;
int tmp = 0;
int i = 0;
priority_queue<int,vector<int>,cmp1> minHeap;			// Set up the minimum priority queue
while (cin >> tmp) {									// Loop in the data stream
if (i < K) {										// Create a K Priority queue size , That is to say K The size of the binary pile
minHeap.push(tmp);
}
else {												// Algorithm implementation
if (tmp <= minHeap.top())
continue;
else if (tmp > minHeap.top()) {
minHeap.pop();
minHeap.push(tmp);
}
}
i++;
}
while (!minHeap.empty()) {								// The biggest output K Number
cout << minHeap.top() << endl;
minHeap.pop();
}
return 0;
}

/* The second case ——Quick Select C++ Code implementation */

/*Quick Select*/
#include <iostream>
#include <vector>

using namespace std;

int Partition(vector<int> &vec, int p, int r) {				// To achieve fast scheduling Partition function , Enter the original array reference , And the left and right subscripts that need to be run
if (p >= r)												// illegal input ,Partition Specific ideas refer to the quick arrangement
return r;
int tmp = vec[r];
int i = p;
int j = p;
while (i < r) {
if (vec[i] <= tmp) {
int temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
i++;
j++;
}
else if (vec[i] > tmp) {
i++;
}
}
vec[r] = vec[j];
vec[j] = tmp;
return j;
}

int main() {
int K = 0;										// Test part , Enter the required K Value size , Then input the array elements in turn
cin >> K;
int tmp = 0;
vector<int> vec;
while (cin >> tmp)
vec.push_back(tmp);
int size = vec.size();
if (size == 0 || k>size) return vector<int>();
if (size== k) return input;
int p = 0;
int r = vec.size() - 1;
int index = Partition(vec, p, r);
while (index != size - K) {						// When Partition The return value and the right part are not K Big hour , Continue to cycle
int sizeOfRight = size - index - 1;			// Record index Right array length size
if (K <= sizeOfRight) {
index = Partition(vec, index + 1, r);
}
else if (K == sizeOfRight + 1)				// This step seems a bit redundant ,while The loop guarantees that , But in order to correspond to the blog text description, I added
continue;
else if (K > sizeOfRight + 1) {
index = Partition(vec, p, index - 1);
}
}
for (int i = index; i < size; i++) {			// Test part , Output what you need K Number
cout << vec[i] << endl;
}
return 0;
}``````

https://chowdera.com/2020/12/202012061742250975.html