algorithm - “稳定”k-最大元素算法

问题描述

相关：空间有限的优先级队列：寻找一个好的算法

我正在寻找一种算法，它从列表中返回 k 最大元素，但不改变 k 最大元素的顺序，例如对于k=4和给定5,9,1,3,7,2,8,4,6，算法应该返回9,7,8,6。

更多背景知识，我的输入数据大约是 200 对(distance,importance)，按 wrt 排序distance，我需要选择其中最重要的 32 个。性能在这里至关重要，因为我必须运行这个选择算法几千次。

到目前为止，我有以下两个想法，但它们似乎都不是最好的。

迭代删除最小元素，直到剩下 32 个元素（即做选择排序）
使用快速选择或中位数来搜索第 32 个最大的元素。然后，再次对剩余的 31 个元素进行排序。

我需要在 C++ 中实现这一点，所以如果有人想编写一些代码并且不知道使用哪种语言，C++ 将是一个选择。

标签： algorithmsortingselection

受@trincot的解决方案的启发，我想出了一个与工作实现略有不同的变体。

算法

使用Floyd 算法来构建最大堆或等效于在 C++ 中使用构造函数构建priority_queue，在该构造函数中我们一次传递整个数组/向量，而不是单独添加元素。如果以 O(N) 时间复杂度构建，则为最大堆。
现在，从最大堆中弹出 K-1 次项目，直到我们得到第 Kth Max Importance Item。将 Kth Max Importance Item 的值存储在变量中Kth_Max_Importance_Item。
扫描原始输入中重要性值大于的所有节点Kth_Max_Importance_Item，并将它们推入输出向量。
Kth_Max_Importance_Item通过从中减去输出向量的当前大小，计算重要性值等于的重要性值的所需项目的剩余计数k。将其存储在变量中left_Over_Count。
从原始输入中扫描left_Over_Count其重要性值等于的重要性值的项目的值的数量Kth_Max_Importance_Item，并将它们推入输出向量。

注意：如果importance值不是唯一的，则该条件由算法的第3步和第 4步处理。

时间复杂度：O(N + K*log(N))。假设 K<<N，那么，时间复杂度 ~ O(N)。

执行：

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>

typedef struct Item{

    int distance;
    double importance;

}Item;

struct itemsCompare{

    bool operator() (const Item& item1, const Item& item2){

        return ((item1.importance < item2.importance) ? true : false);
    }
};

bool compareDouble(const double& a, const double& b){

    return (fabs(a-b) < 0.000001) ? true : false;
}

int main(){

    //Original input
    std::vector<Item> items{{10, 2.1}, {9, 2.3}, {8, 2.2}, {7, 2.2}, {6, 1.5}};

    int k = 4;

    //Min Heap
    std::priority_queue<Item, std::vector<Item>, itemsCompare> maxHeap (items.begin(), items.end());

    //Checking if the order of original input is intact
    /*for(int i=0;i<items.size();i++){
        std::cout<<items[i].distance<<" "<<items[i].importance<<std::endl;
    }*/

    //Pulling the nodes until we get Kth Max Importance Node

    int count = 0;
    while(!maxHeap.empty()){
        
        if(count == k-1){
            break;
        }

        maxHeap.pop();
        count++;

    }

    Item Kth_Max_Importance_Item = maxHeap.top();

    //std::cout<<Kth_Max_Importance_Item.importance<<std::endl;


    //Scanning all the nodes from original input whose importance value is greater than the importance value of Kth_Max_Importance_Item.

    
    std::vector<Item> output;

    for(int i=0;i<items.size();i++){

        if(items[i].importance > Kth_Max_Importance_Item.importance){
            output.push_back(items[i]);
        }
    }
    
    int left_Over_Count = k - output.size();

    //std::cout<<left_Over_Count<<std::endl;

    //Adding left_Over_Count number of values of items whose importance value if equal to importance value of Kth_Max_Importance_Item

    for(int i=0;i<items.size();i++){

        if(compareDouble(items[i].importance, Kth_Max_Importance_Item.importance)){
            output.push_back(items[i]);
            left_Over_Count--;
        }

        if(!left_Over_Count){
            break;
        }
    }

    //Printing the output:

    for(int i=0;i<output.size();i++){

        std::cout<<output[i].distance<<" "<<output[i].importance<<std::endl;
    }

    return 0;
}

输出：

algorithm - “稳定”k-最大元素算法

问题描述

解决方案

推荐阅读