c++ - 使用 STL 仅保留 N 个最小元素(有重复项)

Question

下面的 MVCE 尝试从随机元素(包含重复元素)的大型传入输入流中按升序仅输出 5 个最小元素。

int main(int argc, char *argv[])
{
    std::set<int> s;   //EDIT:  std::multiset is an answer to Q1

    for (int i : {6, 6, 5, 8, 3, 4, 0, 2, 8, 9, 7, 2})  //Billions of elements in reality
    {
        if ( (s.size() < 5) || (i <= *(--s.end())) )  //Insert only if not full or when the element to be inserted is smaller than the greatest one already in the set
        {
            if (s.size() >= 5)  //Limit the number of smallest elements that are kept. In reality ~8000
                s.erase(*(--s.end())); //Erase the largest element

            s.insert(i);
        }
    }

    for (int d: s)
        std::cout << d << " ";  //print the 5 smallest elements in ascending order      

    std::cout << '\n';

    return 0;
}

输出是:

0 2 3 4

输出应该是:

0 2 2 3 4

问题 1:必须更改哪些内容才能允许重复？
问题 2:如何使这段代码更快，同时又不浪费 GB 的内存来存储所有输入元素？ (现在的代码实在是太慢了)。

Answer 1

这听起来像是经典的面试问题“如何在不知道将要处理的数据大小的情况下存储最小的 N 项？”。

一个答案是使用N项的最大堆，然后如果后续项小于或等于中最顶部的项，则调整堆(删除顶部元素，添加新元素，heapify)堆。

这可以使用 C++ 库函数轻松完成 std::make_heap , std::pop_heap , 和 std::push_heap .

这是一个例子:

#include <vector>
#include <algorithm>
#include <iostream>

int main(int argc, char *argv[])
{
    std::vector<int> s; 
    for (int i : {6, 6, 5, 8, 3, 4, 0, 2, 8, 9, 7, 2})
    {
        // add the first 5 elements to the vector
        if (s.size() < 5)
        {
            s.push_back(i);
            if ( s.size() == 5 )
                // make the max-heap of the 5 elements   
                std::make_heap(s.begin(), s.end());
            continue;
        }

        // now check if the next element is smaller than the top of the heap
        if (s.front() >= i)
        {
            // remove the front of the heap by placing it at the end of the vector
            std::pop_heap(s.begin(), s.end());
                   
            // get rid of that item now 
            s.pop_back();

            // add the new item 
            s.push_back(i);

            // heapify
            std::push_heap(s.begin(), s.end());
        }
    }

    // sort the heap    
    std::sort_heap(s.begin(), s.end());

    for (int d : s)
        std::cout << d << " ";  //print the 5 smallest elements in ascending order      

    std::cout << '\n';

    return 0;
}

输出:

0 2 2 3 4

当然你可以把它变成一个函数并替换硬编码的5与 N .

如果有数十亿个元素，即比 N 多得多的元素，则唯一保留在堆中的是 N 个元素。

仅当检测到新项满足成为最小的 N 个元素之一时才对最大堆进行操作，这很容易通过检查堆中的顶部项并将其与正在处理的新项进行比较来完成已处理。

---

如果你想获得 5 个最大的项目，你将构建一个最小堆而不是最大堆。要做到这一点，唯一的改变是调用一个仿函数来改变堆函数中的比较运算符，并将测试改为>=。而不是 <= :

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>

int main(int argc, char *argv[])
{
    std::vector<int> s; 
    for (int i : {6, 6, 5, 8, 3, 4, 0, 2, 8, 9, 7, 2})
    {
        // add the first 5 elements to the vector
        if (s.size() < 5)
        {
            s.push_back(i);
            if ( s.size() == 5 )
                // make the min-heap of the 5 elements   
                std::make_heap(s.begin(), s.end(), std::greater<int>());
            continue;
        }

        // now check if the next element is larger than the top of the heap
        if (s.front() <= i)
        {
            // remove the front of the heap by placing it at the end of the vector
            std::pop_heap(s.begin(), s.end(), std::greater<int>());
                   
            // get rid of that item now 
            s.pop_back();

            // add the new item 
            s.push_back(i);

            // heapify
            std::push_heap(s.begin(), s.end(), std::greater<int>());
        }
    }

    // sort the heap    
    std::sort_heap(s.begin(), s.end(), std::greater<int>());

    for (int d : s)
        std::cout << d << " ";  //print the 5 largest elements in descending order      

    std::cout << '\n';

    return 0;
}

输出:

9 8 8 7 6