c++ - Priority_queue 中的多次插入和删除

Question

问题

在我的算法中，我必须实现一个“有序队列”(我选择这个名称是为了将我心中的想法与现有的实现区分开来)。我必须将一些值插入队列中，其中该值代表队列中的顺序，然后我必须按照顺序消化队列。我感觉我需要做的最好的数据结构是 std::priority_queue ，但我对程序的效率有一些担忧，特别是由于:

• 不提供插入/删除多个元素的方法的接口(interface)
• (可能)类的内部设计及其算法

来自documentation ， priority_queue::push 和 priority_queue::pop 都在内部调用 std::push_heap 和 std::pop_heap ，两者的复杂度均为 O(log(N))。我认为一次插入/删除一个元素，每次调用时都使用底层容器，效率非常低。

为什么要这样实现？也许当你按顺序调用 std::push_heap 和 std::pop_heap 时，底层的堆结构处于最优情况，复杂度相对于 O(log(N)) 降低了？

否则，是否有一个我没有考虑过的最适合我的需求的数据结构？我认为 std::forward_list 也可以满足我的删除需求(通过forward_list::pop_front)，但我担心插入会变得太昂贵，因为我应该找到正确插入位置的迭代器，这应该是 O(N)。

我不想依赖任何外部库(包括 Boost)，因为该项目必须是轻量级且无依赖的。

实现

该程序相当于:

struct MyType{
    double when;
    int who;
    MyType(double t, double i) : when(t), who(i) {};
    bool operator<(const MyType & other) const{ return when < other.when; }
};

using OrderedQueue = priority_queue<MyType,std::vector<MyType>,std::less<MyType>>;

const double TMax = 1e9; // some BIG stopping condition

double some_time(){/*routine to generate the time*/ return TMax * rand(); }

int some_number(){/*routine to generate the number*/ return 100 * rand(); }

void populate(OrderedQueue & q){
    unsigned Ni = 10; // number of insertions: it is not fixed in the real program
    for (auto i = 0; i < Ni; ++i){
        q.emplace(some_time(), some_number());
    }
}

void use_MyType(MyType m){/*routine that uses the top value*/ return; }

void remove(double t, OrderedQueue & q){
    while(q.top().when < t){
        use_MyType(q.top());
        q.pop();
    }
}

int main(){
    double t = 0;
    OrderedQueue q;
    while(t < TMax){
        populate(q);
        remove(t, q);
        t += 1;
    }
}

我对 populate() 和 remove() 的效率特别感兴趣，因为调用它们时的循环有很多次迭代。

Answer 1

std::priority_queue是堆结构的适配器。考虑到您需要按顺序使用元素，堆是最有效的结构。

堆插入最坏情况为O(log(N))，但平均为O(1)。这比例如更快二叉树 ( std::map ) 插入，始终 O(log(N))。类似地，从堆中删除顶部元素是最坏情况 O(log(N))，但平均而言要快得多，因为堆是部分排序的。

话虽如此，现代计算机中分支预测和缓存的影响不容忽视。回答性能问题的最佳方法是使用实​​际数据和代表性元素数对其进行基准测试。我建议使用这 3 个队列结构进行基准测试:

• std::priority_queue<MyType, std::vector<MyType>>
• std::priority_queue<MyType, std::deque<MyType>>
• std::map<MyType>

std::deque作为后备存储可能会提供改进的pop_front性能，但以较慢的随机访问为代价。因此应该对其进行基准测试。

我会忽略std::list ( std::forward_list ) 此时 - 在正确位置插入链表的时间复杂度为 O(N)，而且链表不适合缓存，因此肯定是一个慢得多的解决方案。

有关堆与二叉树性能的更多详细信息，请参阅 this related question .

---

解决您的疑虑:

Interface which does not provide methods for insertions/deletions of multiple elements

将元素插入到堆中涉及将元素追加到末尾并“修复”堆结构。这就是std::push_heap算法确实如此。实现一种算法来以这种方式插入多个元素和/或简单地调用 std::make_heap 是完全可行的。追加多个元素后修复整个堆。

不可能从堆中删除多个元素，因为堆仅相对于第一个(顶部)元素进行排序。移除后，需要调整堆结构以找到下一个顶部元素。这就是std::pop_heap算法确实如此。

Internal design of the class and its algorithms

std::priority_queue只是堆算法的适配器。它是一个方便的类，包装了一个顺序容器并在其上调用堆算法。不是一定要用，可以用std::vector , std::push_heap和std::pop_heap具有完全相同的结果(尽管代码可能可读性较差并且更容易出错)。