educative.io

Educative

Bug: comparator in heap

Because of overflow/underflow, (a, b) -> a-b is broken, for example a = Integer.MAX_VALUE and b = Integer.MIN_VALUE gives a < b. We should use (a, b) -> Integer.compare(a, b). Also the default PriorityQueue in Java is minHeap so for that we do not need to pass in a comparator.

To insert a number, the two heap solution takes 3*lgN in the worst case whereas a BinarySearchTree(BST) takes logN - assuming the input numbers are random thus BST is balanced. True, findMedian takes lgN with BST, but probably findMedian would be called much less frequently than insertNum so BST might perform better on an average.