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 `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) 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, Aug 03 '18 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, Aug 04 '18 at 03: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, Aug 04 '18 at 15:40

NathanOliver · Answer 1 · 2018-08-04T03:17:30.803

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 04 '18 at 03:17

answered Aug 03 '18 at 19:30

NathanOliver

171,901
28
288
402

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 – Falcon Aug 04 '18 at 03:13
@falcon I've revised the code. I think that is closer to what you want. – NathanOliver Aug 04 '18 at 03:18
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. – Falcon Aug 04 '18 at 03:39

Unexpected behaviour of Priority_queue size

1 Answers1