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.
#include<iterator> //istream_iterator#include<cstdio> //printf#include<vector> //base container for heap#include<iostream> //cin#include<algorithm> //minmax#include<functional> //std::greater#include<queue> //heapusingnamespacestd;template<classT,template<class>classCmp=less>usingheap=std::priority_queue<T,vector<T>,Cmp<T>>;//from <queue>structmed//streamed median class{doubleoperator()()const;//get current medianmed&operator<<(intv);//insert a valueprivate:heap<int,less>maxh;//maxheapheap<int,greater>minh;//minheap};intmain(){medm;//streamed median objectfor_each(//for each int streamed in from stdin++istream_iterator<int>(cin),//preincrement to toss out unneeded first entryistream_iterator<int>(),[&m](constint&n){printf("%.1f\n",(m<<n)());//print value of median after inserting current int});return0;}//get current mediandoublemed::operator()()const{if(maxh.size()==minh.size()&&maxh.size()>0)return0.5*(maxh.top()+minh.top());else{//find bigger heapif(maxh.size()>minh.size())return1.0*maxh.top();elseif(minh.size()>maxh.size())return1.0*minh.top();elsereturn0.0;//both heaps empty}}//insert a valuemed&med::operator<<(intv){if(maxh.empty()||v<=maxh.top())maxh.push(v);elseminh.push(v);//now, rebalance//subtr with unsigned vals gets trickypair<unsignedlong,unsignedlong>//auto keyword fails bigtime heree=minmax(maxh.size(),minh.size());if(e.second-e.first>1){//find bigger heap, plop the extra into the smaller heapif(maxh.size()>minh.size()){minh.push(maxh.top());maxh.pop();}else{maxh.push(minh.top());minh.pop();}}return*this;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →