C++ Priority Queue - ordering intervals

Question

Given initially a time interval. Every time, we pick the largest interval and split that into two halves. If there is a tie, then we pick the interval with the lowest starting point.

for example - [0,9] first split - P1 [0,4] and P2 [4,9]

For second split : dist(P1) = 3 => if pick P1, new intervals would be [0,2] and [2,4]. dist(P2) = 4 => if pick P2, new intervals are [4, 6] and [6,9] In both the cases, we have to create sub interval of distance 1. So, it's a tie. and, we pick P1 as P1 < P2.

[0,2], [2, 4], [4, 9]

Third Split: [0,2], [2, 4], [4,6], [6,9]

Fourth Split: There is a tie, s0, picked [0,2] [0,1], [1,2], [2,4], [4,6], [6, 9]

Fifth Split: [0,1], [1,2], [2,3], [3,4], [4,6], [6,9]

a possible candidate to be on the top : [4,6]

But, I always get [1,2] on top.

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    auto dist{ [](const auto & p) {
        return p.second - p.first - 1;
    } };
    auto comp{ 
        [&dist](const auto & p1, const auto & p2) {
            if (abs(dist(p1) - dist(p2)) <= 1) {
                return p1.first > p2.first;
            }
            return dist(p1) < dist(p2);
        }
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> maxQ{comp};
    maxQ.push({ 0, 9 }); // initial interval
    for (int i{ 0 }; i < 5; ++i) {
        auto ii{ maxQ.top() };
        maxQ.pop();
        int mid = (ii.first + ii.second) / 2;
        maxQ.push({ ii.first, mid });
        maxQ.push({ mid, ii.second });
    }

    while (!maxQ.empty()) {
        auto& ii{ maxQ.top() };
        cout << ii.first << " : " << ii.second << endl;
        maxQ.pop();
    }
}

I'm getting the following output :

IMO, 1 : 2 interval shouldn't be on top. Could someone help me here, why is it so.

EnigmaticBacon · Answer 1 · 2020-12-10T21:15:38.653

It turns out that this issue has more to do with how priority queues comparators are designed, refer to The reason of using `std::greater` for creating min heap via `priority_queue`

The gist of it is that when two nodes are compared, if the comparator returns true, p1 will fall below p2. So a basic ">" comparator, will have smaller nodes at the top, and bigger nodes at the bottom.

To visualize the issue, I ran through it in a debugger, this is the moment at which the (1,2) is being put above (6,9). This is the current state of the priority queue:

We see that (2,4) is in front (6,9), which is expected since our comparison function says that (2,4) < (6,9) as explained above.

Then, the code goes to pop the top of the priority queue, meaning replaces (2,4) with the new biggest interval. How priority queues in C++ do this, is they swap the first element and last elements of the heap, and then reduce the size of it by 1 (so we lose the original first element).

So after the swap and size reduction, our heap looks like this:

Then, since the previously deemed smallest element is now at the top of the queue, we need to find its rightful spot.

So (1,2) is going to look at its children, (6,9) and (4,6), and see which is more important.

With our comparison operator, (4,6) is the more important node.

It then compares, (1,2) with the most important of the previous two nodes, (4,6), to see if it needs to perform a swap to make the queue valid.

It then finds that (1,2) is more important because 1 < 4. Thus, (1,2) stays in its spot and we're left with:

Thanks for the response. Here I picked the initial interval [0,9]. first split - P1 [0,4] and P2 [4,9] For second split : dist(P1) = 3 => if pick P1, new intervals would be [0,2] and [2,4]. dist(P2) = 4 => if pick P2, new intervals are [4, 6] and [6,9] in both the cases, we have to create sub interval of distance 1. So, it's a tie. and, we pick P1 as P1 < P2. — panky, Dec 10 '20 at 20:25
Right, the issue is it leads to cascading problems like the one you're facing. I'll edit my comment to work through it step by step. — EnigmaticBacon, Dec 10 '20 at 20:31

Asteroids With Wings · Accepted Answer · 2020-12-10T20:51:33.460

We can plainly see that [1,2] is ordered before [4,6], by plugging it into your comparator:

comp([1,2], [4,6])
  if (abs(dist([1,2]) - dist([4,6])) <= 1) {   // abs(0 - 1) <= 1   or  1 <= 1
    return 1 > 4;   //  false
  }
  return dist([1,2]) < dist([4,6]);   //  not reached

Only you can correct the comparator to achieve whatever your goal is here, but the existing code is wrong if you want [1,2] to be ordered after [4,6].

At a guess, though, based on your description, you might try:

if (abs(dist(p1)) == abs(dist(p2)))

But I'd go to some lengths to ensure that your ordering is strict weak as it must be for the container. Sprinkling some more abs around may help.

Overall this is quite a complex comparator that's not easy to understand at a glance.

Thanks. This makes lots of sense now. I can see the problem here. — panky, Dec 10 '20 at 20:51

score 0 · Answer 3 · answered Dec 10 '20 at 20:47

0

I think It is because the ordering of intervals is not strict. e.g. P1(0,1), P2(4,6) and P3(6,9)

P1 should come before P2. P2 should come before P3. P3 should come before P1.

That's crazy. How could I set a strict pair ordering here?

answered Dec 10 '20 at 20:47

panky

50
4

You could do it by performing a linear search. – EnigmaticBacon Dec 10 '20 at 21:34

C++ Priority Queue - ordering intervals

3 Answers3