We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
functionmain(){varn=parseInt(readLine());varl=[];// build a max heapvarr=[];// build a min heapvarmid=0;// the value above the min and max heapsvaroutformat=newIntl.NumberFormat('en-US',{useGrouping:false,minimumFractionDigits:1,maximumFractionDigits:1})constheapBubble=(h,comp,i)=>{if(i>0){letp_i=Math.floor((i-1)/2)if(comp(h[i],h[p_i])){[h[i],h[p_i]]=[h[p_i],h[i]];heapBubble(h,comp,p_i);}}}constaddToL=(v)=>{l.push(v);heapBubble(l,(a,b)=>+a>+b,l.length-1)// l.sort((a,b) => a-b)}constaddToR=(v)=>{r.push(v);heapBubble(r,(a,b)=>+a<+b,r.length-1)// r.sort((a,b) => a-b)}constheapSink=(h,comp,i)=>{if(i<h.length){letv=h[i]lettarget=i;letc1=Math.floor(i*2+1)letc2=c1+1//// complicated process}}constreplaceRHead=(v)=>{r[0]=r.pop()heapSink(r,(a,b)=>+a<+b,0)addToR(v);}constreplaceLHead=(v)=>{l[0]=l.pop()heapSink(l,(a,b)=>+a>+b,0)addToL(v);}mid=parseInt(readLine());console.log(outformat.format(mid))for(vara_i=1;a_i<n;a_i++){letval=parseInt(readLine());if((a_i%2)===1){// the first value for exampleif(val>mid){addToL(mid);addToR(val);}else{addToR(mid);addToL(val);}mid=-1;console.log(outformat.format((+l[0]++r[0])/2))}else{if(val>r[0]){mid=r[0];replaceRHead(val)}elseif(val<l[0]){mid=l[0];replaceLHead(val);}else{// mid is the median elementmid=val;}console.log(outformat.format(mid))}}}
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
The nightmare that is using JavaScript on HackerRank...
Thanks to this guy for some help with heap deletion. http://blog.mattblair.co/