-
Notifications
You must be signed in to change notification settings - Fork 0
/
Running Median
59 lines (55 loc) · 1.13 KB
/
Running Median
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution
{
public:
priority_queue <int> ls;
priority_queue<int, vector<int> , greater<int>> rs;
//Function to insert heap.
void insertHeap(int &x)
{
bool l = true ;
if(ls.size() == 0)
{
ls.push(x);
return ;
}
if(x > ls.top())
l = false;
if(l)
ls.push(x) ;
else
rs.push(x) ;
balanceHeaps() ;
}
//Function to balance heaps.
void balanceHeaps()
{
if(ls.size() > rs.size() + 1 )
{
int a = ls.top() ;
rs.push(a) ;
ls.pop() ;
}
else if(rs.size() > ls.size() + 1)
{
int a = rs.top() ;
ls.push(a) ;
rs.pop() ;
}
}
//Function to return Median.
double getMedian()
{
if(ls.size() == rs.size())
{
return (ls.top() + rs.top()) / 2 ;
}
else if(ls.size() > rs.size())
{
return ls.top() ;
}
else
{
return rs.top() ;
}
}
};