Unexpected behaviour of Priority_queue size

Question

I was writing the code for the problem. Median of the stream of integers when I encountered an issue. Note that this issue is not the algorithmic but rather ambiguous behavior of the priority_queue size.

#include <bits/stdc++.h> using namespace std; priority_queue<double> small; priority_queue<double, vector<double>, greater<double> > large; void rebalance() { cout << "Initial size\n"; cout << "small " << small.size() << " large " << large.size() << endl; if (small.size() - large.size()>1) { large.push(small.top()); small.pop(); } else if (large.size() - small.size()>1) { cout << "Unexpectedly goes here\n"; cout << "garbage size difference " << large.size() - small.size() << endl; small.push(large.top()); large.pop(); } } void addNum(int num) { if (small.size() == 0 || num<small.top()) { small.push(num); } else { large.push(num); } rebalance(); } double findMedian() { if (small.size() == large.size()) { double ans = (small.top() + large.top()) / 2.0; return ans; } else if (small.size()>large.size()) { return (double)small.top(); } else { return (double)large.top(); } } int main() { std::ios_base::sync_with_stdio(false); int num = 5; addNum(num); cout << findMedian() << endl; return 0; }

The output for this code is

 Initial size small 1 large 0 Unexpectedly goes here garbage size difference 18446744073709551615 fish: “./a.out” terminated by signal SIGSEGV (Address boundary error)

In the rebalance function the initial size of small is 1 and large is 0 which suggest that the loop should neither enter the if condition nor the else if condition but the loop enters the else if condition with a garbage value in size.why does this happen? Moreover I tried saving the small and large size in an integer variable and then comparing them in conditionals,which lead to acceptance of the code. Hence the algorithm handles the correctness.

What leads to this garbage value?

Separately #include <bits/stdc++.h> and using namespace std; are bad practice. Together they magnify each other's worst ill effects. Be very cautious. If you start encountering insane mystery errors, one of the first things you should do is remove these two lines. — user4581301
– user4581301, Commented Aug 3, 2018 at 19:37
@user4581301 why is it so though? Competitive programmers have been using these two lines to reduce a lot of boilerplate libraries and std:: — Falcon
– Falcon, Commented Aug 4, 2018 at 3:07
There are tens of thousands of identifiers in the standard library. Far more than you need for any program. Including the entire standard library brings them all into your program where they can conflict with the identifiers you define. Fortunately they are in the std namespace and require scope resolution. And then along comes using namespace std to remove that protection. How much time are you willing to spend on figuring out why the compiler's telling you that your polynomial function laguerre is ambiguous? Show caution. — user4581301
– user4581301, Commented Aug 4, 2018 at 15:40

NathanOliver · Accepted Answer · 2018-08-04 03:17:30Z

2

In

else if(large.size()-small.size()>1)

size() returns an unsigned number. A unsigned number can never be negative so if would be a negative number it wraps around to the largest number it could be and then goes backwards from there. Since large has a size of 0 and small has a size of 1 then 0 - 1 gives you 18446744073709551615. I believe what you are trying to do should be expressed as

if(small.size() < large.size()) { small.push(large.top()); large.pop(): } else if(large.size() < small.size()) { large.push(small.top()); small.pop(); }

edited Aug 4, 2018 at 3:17

answered Aug 3, 2018 at 19:30

NathanOliver

183k29 gold badges323 silver badges439 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Falcon Over a year ago

I understood your explanation but the changes suggested by you won't lead to a correct solution I guess since for the first element pushed small.size()>large.size() hence the code goes in else if and pops from large which is empty therefore producing Seg fault. We only have to rebalance when the difference between sizes is more than one, so I guess storing in variables might be a simple way which passes all the cases. I am pretty amused by the behavior for size() though. Thanks

NathanOliver Over a year ago

@falcon I've revised the code. I think that is closer to what you want.

Falcon Over a year ago

Still fails for a test case :(. we only need to balance when size_diff >=2. so i surrounded the a.size - abs(b.size())>1 in both conditional,hence it passes.

Collectives™ on Stack Overflow

Unexpected behaviour of Priority_queue size

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related