You mentioned that a heap is a complete binary tree. A binary tree takes n log n to create while a heap takes n. If a heap took n log n then we would have no benefit of using the heap in this situation. Does that sound reasonable?
class MedianFinder { public: MedianFinder() { } priority_queuemaxheap; priority_queueminheap; void addNum(int num) { if(maxheap.empty()&&minheap.empty()) maxheap.push(num); else{ if(num>maxheap.top()) minheap.push(num); else maxheap.push(num); } int m=maxheap.size(); int n=maxheap.size(); if(m-n==2||m-n==-2){ if(m>n){ int k=maxheap.top(); maxheap.pop(); minheap.push(k); }else{ int k=minheap.top(); minheap.pop(); maxheap.push(k); } } } double findMedian() { int m=maxheap.size(); int n=maxheap.size(); if((m+n)%2==0) return ((double)maxheap.top()+(double)minheap.top())/2; if(m>n) return maxheap.top(); else return minheap.top(); } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */ please tell me what is wrong in the above code..
Hey i have the same doubt it's giving runtime error By the way while dividing you should divide by 2.0 instead of 2 Can you please tell me if you have resolved the error?
