where is wrong with my java code? Please help.


  • 0
    I

    Who can tell me where is wrong with my code.
    I am trying to write the heap myself, but I can pass the 12th test case and I can't figure out where is wrong. Please help me with my code.

    public class MedianFinder {
        Heap maxHeap = new Heap(true);
        Heap minHeap = new Heap(false);
        boolean even = true;
        // Adds a number into the data structure.
        public void addNum(int num) {
            if(even){
                Integer maxTop = maxHeap.getTop();
                if(maxTop != null && maxTop > num){
                    maxHeap.deleteTop();
                    maxHeap.insert(num);
                    minHeap.insert(maxTop);
                }else{
                    minHeap.insert(num);
                }
                even = !even;
            }else{
                Integer minTop = minHeap.getTop();
                if(minTop != null && minTop <num){
                    minHeap.deleteTop();
                    minHeap.insert(num);
                    maxHeap.insert(minTop);
                }else{
                    maxHeap.insert(num);
                }
                even =!even;
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if(even){
                int maxTop = maxHeap.getTop();
                int minTop = minHeap.getTop();
                double median = (maxTop+minTop)/2.0;
                return median;
            }else{
                double median = minHeap.getTop();
                return median;
            }
        }
        class Heap{
            boolean max = true;
            private List<Integer> list = new ArrayList<Integer>();
            Heap(boolean max){
                this.max = max;
            }
            public void insert(int num){
                list.add(0,num);
                siftDown(0);
            }
            
            public Integer deleteTop(){
                if(list.isEmpty()) return null;
                if(list.size() == 1) return list.remove(0);
                int first = list.get(0);
                int tail = list.remove(list.size()-1);
                list.set(0,tail);
                siftDown(0);
                return first;
            }
            public Integer getTop(){
                if(list.isEmpty()) return null;
                else return list.get(0);
            }
            private void siftDown(int index){
                if(max){
                    siftDownMax(index);
                }else{
                    siftDownMin(index);
                }
            }
         
            private void siftDownMax(int index){
                int half = list.size()/2;
                while(index < half){
                    int left = index*2+1 > list.size()-1 ? index:index*2+1 ;
                    int right = index*2+2 > list.size()-1 ? index:index*2+2;
                    int change = list.get(left) > list.get(right) ? left:right;
                    if(list.get(index) >= list.get(change)) return;
                    int temp = list.get(change);
                    list.set(change,list.get(index));
                    list.set(index,temp);
                    index = change;
                }
            }
          
            private void siftDownMin(int index){
                int half = list.size()/2;
                while(index < half){
                    int left = index*2+1 > list.size()-1? index: index*2+1;
                    int right = index*2+2 > list.size()-1 ? index: index*2+2;
                    int change = list.get(left) < list.get(right) ? left:right;
                    if(list.get(index) <= list.get(change) ) return;
                    int temp = list.get(change);
                    list.set(change,list.get(index));
                    list.set(index,temp);
                    index = change;
                }
            }
        }
    
    };
    
    

Log in to reply
 

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