How to merge two priority_queue?

Question

I have two priority_queue with float like this:

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

And I need to merge them. But STL merge algorithm do not allow working with the priority_queue directly:

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

Is there a way to merge priority_queue without using auxiliary data structures?

I'm afraid you will have to pop elements from one queue and push them into the other one. — juanchopanza, Apr 06 '13 at 14:59
The standard library doesn't contain an algorithm to merge two heaps. Since `priority_queue` is just a wrapper around the standard library's heap algorithms, you don't have a merge feature. — Kerrek SB, Apr 06 '13 at 15:01

score 6 · Answer 1 · answered Sep 20 '18 at 02:26

Adding to Andy's answer, an important optimization is to always merge elements from the smaller priority queue into the larger one. This can be done using 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();
  }
}

This can make a real difference, especially when the two priority queues have very different sizes.

In the most recent Facebook Hacker Cup programming contest, there was a question that required you to merge priority queues as part of a larger algorithm. If you didn't do this optimization, your code would take too long and you would not get the question correct. This happened to me; my code took over 5 minutes to run without this optimization, but less than 10 seconds when I added this optimization after the contest was over. I did not receive credit for the question. Hopefully if you're reading this and encounter a similar problem you'll be more successful :)

score 5 · Accepted Answer · answered Apr 06 '13 at 14:59

priority_queue is a container adapter, not a regular standard container. In particular, it does not offer the begin() and end() member functions. Therefore, you will have to pop the elements out of one queue and push them into the other:

while (!queue2.empty())
{
    queue1.push(queue2.top());
    queue2.pop();
}

score 2 · Answer 3 · answered Sep 20 '18 at 05:43

Instead of processing them one by one, as suggested before, to achieve better performance you can "steal" underlying containers from queues, merge them and construct another priority_queue from the merged container:

// https://stackoverflow.com/a/1385520/8414561
template <class T, class S, class C>
S& Container(std::priority_queue<T, S, C>& q) {
    struct HackedQueue : private std::priority_queue<T, S, C> {
        static S& Container(std::priority_queue<T, S, C>& q) {
            return q.*&HackedQueue::c;
        }
    };
    return HackedQueue::Container(q);
}

int main()
{
    std::priority_queue<int> queue1{std::less<int>{}, {1,2,3,4,5,6,7}};
    std::priority_queue<int> queue2{std::less<int>{}, {10,14,15}};

    auto v1 = std::move(Container(queue1));
    auto v2 = std::move(Container(queue2));

    v1.insert(v1.end(), std::make_move_iterator(v2.begin()), std::make_move_iterator(v2.end()));

    std::priority_queue<int>queue3{std::less<int>{}, std::move(v1)};
    while (!queue3.empty()) {
        std::cout << queue3.top() << std::endl;
        queue3.pop();
    }
}

Live example.

How to merge two priority_queue?

3 Answers3

Linked

Related