-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
36 lines (33 loc) · 887 Bytes
/
Program.cs
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
var heap = new MedianFinder();
heap.AddNum(1);
heap.AddNum(2);
Console.WriteLine(heap.FindMedian());
heap.AddNum(3);
Console.WriteLine(heap.FindMedian());
public class MedianFinder
{
PriorityQueue<int, int> minHeap;
PriorityQueue<int, int> maxHeap;
public MedianFinder()
{
minHeap = new PriorityQueue<int, int>();
maxHeap = new PriorityQueue<int, int>();
}
public void AddNum(int num)
{
minHeap.Enqueue(num, num);
var min = minHeap.Dequeue();
maxHeap.Enqueue(min, -min);
if (maxHeap.Count > minHeap.Count)
{
var max = maxHeap.Dequeue();
minHeap.Enqueue(max, max);
}
}
public double FindMedian()
{
if (minHeap.Count == maxHeap.Count)
return ((double)minHeap.Peek() + maxHeap.Peek()) / 2;
return (double)minHeap.Peek();
}
}