-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapTest.h
More file actions
50 lines (45 loc) · 959 Bytes
/
HeapTest.h
File metadata and controls
50 lines (45 loc) · 959 Bytes
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
#pragma once
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class HeapToMedian
{
public:
vector<int> Left;
vector<int> Right;
void Insert(int nNum);
protected:
private:
};
void HeapToMedian::Insert(int nNum)
{
int nCount1 = Left.size();
int nCount2 = Right.size();
if ((nCount1 + nCount2) % 2 == 1)
{
if (Left.size() > 0 && nNum > Left[0])
{
Left.push_back(nNum);
push_heap(Left.begin(), Left.end(), greater<int>);
nNum = Left[0];
pop_heap(Left.begin(), Left.end(), greater<int>);
Left.pop_back();
}
Right.push_back(nNum);
push_heap(Right.begin(), Right.end(), less<int>);
}
else
{
if (Right.size() > 0 && nNum > Right[0])
{
Right.push_back(nNum);
push_heap(Right.begin(), Right.end(), greater<int>);
nNum = Right[0];
pop_heap(Right.begin(), Right.end(), greater<int>);
Right.pop_back();
}
Left.push_back(nNum);
push_heap(Left.begin(), Left.end(), less<int>);
}
}