根据此处找到的答案,https://stackoverflow.com/a/10931091/1311773 ,我正在尝试实现两个堆,以便计算运行中位数。
我不熟悉堆,我不确定从哪里开始实现这里描述的这个功能。 http://programmingpraxis.com/2012/05/29/streaming-median/
我的目标是创建一个小型测试程序来有效地计算运行中位数,这样随着列表的增长,中位数不需要从头开始重新计算。使用两个堆,我应该能够做到,我只是对如何开始实现它犹豫不决。
如有任何建议,我们将不胜感激。
最佳答案
std::priority_queue
模板提供堆的所有属性。恒定时间最大值或最小值提取(取决于项目的比较方式)和对数时间插入。它可以在 <queue>
中找到头文件。
默认情况下,priority_queue
是最大堆。
int numbers[11] = { 0, 9, 3, 4, 8, 12, 2, 11, 10, 1, 5 };
std::priority_queue<int> myheap(numbers, numbers + 11);
std::cout << "biggest " << myheap.top() << std::endl; // 12
myheap.pop();
std::cout << "biggest " << myheap.top() << std::endl; // 11
myheap.push(6);
std::cout << "biggest " << myheap.top() << std::endl; // 11
myheap.push(13);
std::cout << "biggest " << myheap.top() << std::endl; // 13
下面是一个如何创建最小堆的例子:
std::priority_queue<
int,
std::priority_queue<int>::container_type,
std::greater<int>
>;
实现流式中值算法,方法类似这样:
- 为小于中位数的项目创建最大堆
- 为大于中位数的项目创建一个最小堆
- 将新项目插入堆时
- 决定应该把它推到哪个堆,然后把它推到那里
- 如果其中一个堆的大小比另一个堆大 1 以上,则弹出较大的堆,并将该元素放入较小的堆中
然后,中位数是较大堆的顶部,或者是两个堆顶部的平均值。
如果您觉得需要手动管理堆,C++
提供允许您在自己的随机访问数据结构上执行此操作的算法。
-
std::make_heap
-- 堆化由迭代器端点指定的区域 -
std::push_heap
-- 假设前N-1个元素已经是堆,将第N个元素合并到堆中 -
std::pop_heap
-- 将区域中的第一个元素放到最后一个位置,并重新堆化区域,但保留最后一个元素
关于C++实现堆中值函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10966298/