作业: 要求输入$i$个数字时候计算这$i$个数字的中位数。
堆的实现利用了c++的make_heap(),sort_heap函数,类似优先队列。
- 最小堆的实现代码:
/**************最小堆**********/
class MinHeap
{
public:
void createHeap()
{
make_heap(heap.begin(), heap.end()); //堆化
sort_heap(heap.begin(), heap.end());//排序
}
/**************每次插入一个元素后需要对整体进行排序,维持优先序列特性*****************/
void push(int i)
{
heap.push_back(i);//插入
createHeap();//排序,最小值为第一个元素
}
int top()
{
return heap[0];//返回最小值
}
/***************返回最最小值中的最后一个元素**************/
int back()
{
int a = heap[heap.size()-1];
// heap.pop_back();
return a;
}
int size()
{
return heap.size();
}
void print()
{
for(auto i : heap)
{
cout << i << " ";
}
cout << endl;
}
/**************删除最后的一个元素,即最小堆中最大元素************/
void pop()
{
heap.pop_back();
}
public:
vector<int> heap;
};
View Code
2. 最大堆的实现代码:
class MaxHeap
{
public:
void createHeap()
{
make_heap(heap.begin(), heap.end());
sort_heap(heap.begin(), heap.end());
reverse(heap.begin(), heap.end());//首元素为最大一个元素
}
/**************每次插入一个元素后需要对整体进行排序,维持优先序列特性*****************/
void push(int i)
{
heap.push_back(i);
createHeap();
}
/************返回最大的元素************/
int top()
{
return heap[0];
}
int back()
{
int a = heap[heap.size()-1];
// heap.pop_back();
return a;
}
/*****************删除最后一个元素********************/
void pop()
{
heap.pop_back();
}
int size()
{
return heap.size();
}
void print()
{
for(auto i : heap)
{
cout << i << " ";
}
cout << endl;
}
public:
vector<int> heap;
};
View Code
3. 求中位数的步骤:输入第i个数字时:
(1) i个元素中较大值的一半放在最大堆中,较小的一半部分放在最小堆中
(2) 需要维持两个堆的大小平衡。
(3) 中位数分布在最大堆的尾元素和最小堆的尾元素。
(4) 插入元素j时,j > Max_heap_min,放入最大堆, j < Min_heap_max,放入最小堆。
(5)分布在两个值之间则随便放,单需要控制两个堆的平衡。
c++代码如下:
/****************输入第i个元素时,计算此时的i个元素的中位数****************/
class Median
{
public:
void get_data(MaxHeap &maxheap, MinHeap &minheap)
{
ifstream fin("Median.txt");
string line;
stringstream stream;
int count = 1;
while(getline(fin, line))
{
int data;
stream.clear();
stream << line;
stream >> data;
_storage.push_back(data);
median(data, maxheap, minheap);
count ++;
}
}
void median(int data, MaxHeap &maxheap, MinHeap &minheap)
{
if(_storage.size() == 1) //只有一个元素的情况
{
_median.push_back(data);
} else if(_storage.size() == 2) { //只有两个元素
if(_storage[0] < _storage[1])
{
_median.push_back(_storage[0]);
maxheap.heap.push_back(_storage[1]);
minheap.heap.push_back(_storage[0]);
} else {
_median.push_back(_storage[1]);
maxheap.heap.push_back(_storage[0]);
minheap.heap.push_back(_storage[1]);
}
} else { //两个以上元素
int max = minheap.back();
int min = maxheap.back();
if(data > min)
{
maxheap.push(data);
} else {
minheap.push(data);
}
balance(maxheap, minheap);
if(minheap.size() >= maxheap.size())
{
_median.push_back( minheap.back() );
} else {
_median.push_back( maxheap.back() );
}
}
}
/*******************保持两个堆数目的平衡*******************/
void balance(MaxHeap &maxheap, MinHeap &minheap)
{
int size1 = maxheap.size();
int size2 = minheap.size();
if(size1 - size2 == 2)
{
//取出最大堆中最后一个元素放入最小堆
int temp = maxheap.back();
maxheap.pop();
minheap.push(temp);
} else if (size2 - size1 == 2){
int temp = minheap.back();//最后一个元素
minheap.pop();//删除最后一个元素
maxheap.push(temp);//将最后一个元素放入最大堆
} else {
;
}
}
void write()
{
ofstream fout;
fout.open("output.txt");
for(int i = 0; i < _median.size(); i++)
{
fout << "[" << i << "]:" << _median[i] << endl;
}
}
void modo()
{
int sum = 0;
for(auto i : _median)
{
sum += i;
}
cout << sum % 10000;
}
public:
vector<int> _median;
vector<int> _storage;
};
View Code
完整代码:
https://github.com/Shinered/Median-/blob/master/Median.cpp
原文链接: https://www.cnblogs.com/Shinered/p/9029698.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/273828
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!