[java/?/heap] lambda 99ms, Collections.reverse() 31ms, can someone explain?


  • 0

    Using lambda to maxheap will lead to 99 ms, while...weird....

    private PriorityQueue<Integer> right = new PriorityQueue<>();
        // max, Collections.reverseOrder() 31ms
        private PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        // lambda 99ms
        //private PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        // Adds a number into the data structure.
        public void addNum(int num) {
            if (left.isEmpty()) {
                left.add(num);
                return;
            }
    
            if (num <= left.peek()) {
                if (left.size() > right.size()) {
                    right.add(left.poll());
                }
                left.add(num);
            } else {
                if (right.size() == left.size()) {
                    if (num <= right.peek())
                        left.add(num);
                    else {
                        left.add(right.poll());
                        right.add(num);
                    }
                } else
                    right.add(num);
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (left.size() > right.size()) {
                return (double) left.peek();
            } else
                return (left.peek() + right.peek()) / 2.0;
        }
    

Log in to reply
 

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