Never create max heap in java like this...


  • 0

    I spent 2 hours debugging my code because I couldn't pass the last test case:

    [-2147483648,-2147483648,2147483647,-2147483648,1,3,-2147483648,-100,8,17,22,-2147483648,-2147483648,2147483647,2147483647,2147483647,2147483647,-2147483648,2147483647,-2147483648]
    6
    

    Finally, I found out why:

    I created my max heap like this:

    PriorityQueue<Integer> max = new PriorityQueue<Integer>(1, new Comparator<Integer>(){
        @Override
        public int compare(Integer x, Integer y){
            return y-x;
        }
    });
    

    seems pretty standard right? I always create max heap like this in java

    It works correctly most of the time, however, consider this case: x = 1, y=-2147483648, now y-x will cause overflow, y-x=2147483647 which is the wrong result.

    Damn, I'm stupid.. ( ˉ ⌓ ˉ ๑)

    For those who creates max heap like this, please don't do it again, create max heap correctly as follows:

    PriorityQueue<Integer> max = new PriorityQueue<>(1, Collections.reverseOrder());
    

    or like this:

    PriorityQueue<Integer> max = new PriorityQueue<Integer>(1, new Comparator<Integer>(){
        @Override
        public int compare(Integer x, Integer y){
            return y.compareTo(x);
        }
    });
    

    Please vote this if you made the same mistake as I did.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.