c++ - 如何合并两个priority_queue？

Question

我有两个 priority_queue 和 float 像这样:

std::priority_queue<float> queue1;
std::priority_queue<float> queue2;

我需要合并它们。但是 STL merge 算法不允许直接使用 priority_queue:

merge(
  queue1.begin(), queue2.end(),
  queue2.begin(), queue2.end(),
  queue1
);

有没有办法不使用辅助数据结构来合并priority_queue？

Answer 1

添加到 Andy 的答案中，一个重要的优化是始终将较小优先级队列中的元素合并到较大优先级队列中。这可以使用 std::swap 来完成:

// merge elements into dest from src
template<typename T>
void merge_pq(std::priority_queue<T>& dest, std::priority_queue<T>& src) {
  if (dest.size() < src.size()) {
    std::swap(dest, src);
  }
  while (!src.empty()) {
    dest.push(src.top());
    src.pop();
  }
}

这会带来真正的不同，尤其是当两个优先级队列的大小非常不同时。

在最近的 Facebook 黑客杯编程竞赛中，有一个问题要求您将优先级队列合并为更大算法的一部分。如果您不进行此优化，您的代码将花费太长时间并且您将无法正确回答问题。这发生在我身上；如果没有此优化，我的代码运行时间超过 5 分钟，但在比赛结束后添加此优化后，我的代码运行时间不到 10 秒。我没有得到这个问题的功劳。希望如果您正在阅读本文并遇到类似的问题，您会更加成功:)