C ++实现堆中位数功能 [英] C++ Implementing Heap Median Function

问题描述

按照此处找到的答案 https://stackoverflow.com/a/10931091/1311773 ，我正在尝试实现两个堆，以便我可以计算运行中位数.

Following the answer found here, https://stackoverflow.com/a/10931091/1311773, I am attempting to implement two heaps so I can calculate a running median.

我不熟悉堆，并且不确定从何处开始实现此处描述的此功能. http://programmingpraxis.com/2012/05/29/streaming-median/

I'm unfamiliar with heaps, and am not sure where to begin implementing this function described here. http://programmingpraxis.com/2012/05/29/streaming-median/

我的目标是创建一个小的测试程序，以高效地计算运行中位数，因此随着列表的增加，不需要从头开始重新计算中位数.使用两个堆，我应该能够做到，我只是对如何开始实现它感到不知所措.

My goal is to create a small test program that calculates running medians efficiently, so as the list grows the median doesn't need to be recalculated from scratch. Using two heaps, I should be able to do it, I'm just shaky on how to start implementing it.

对此有任何建议.

推荐答案

std::priority_queue模板提供堆的所有属性.恒定时间的最大或最小提取时间(取决于比较项目的方式)，以及对数时间插入.可以在<queue>头文件中找到.

The std::priority_queue template provides all the properties of a heap. Constant time maximum or minimum extraction (depending on how the items are compared), and logarithmic time insertion. It can be found in the <queue> header file.

默认情况下，priority_queue是最大堆.

By default, the priority_queue is a max-heap.

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

以下是如何创建最小堆的示例:

Here is an example of how to create a min-heap:

std::priority_queue<
    int,
    std::priority_queue<int>::container_type,
    std::greater<int>
>;

要实现流中值算法，该方法类似于此:

To implement the streaming median algorithm, the approach is similar to this:

• 为小于中位数的商品创建最大堆
• 为大于中位数的商品创建最小堆
• 将新项目推入堆中时
  • 确定应将其推入哪个堆，然后将其推入那里
  • 如果其中一个堆的大小大于另一个堆的大小，则弹出较大的堆，然后将该元素放入较小的堆
  • create a max-heap for items that are smaller than the median
  • create a min-heap for items that are greater than the median
  • when pushing new items into the heap
    • decide which heap it should be pushed into, and push it there
    • if one of the heaps' size is more than 1 greater than the other heap, then pop the bigger one, and put that element into the smaller one

    然后，中值要么是较大堆的顶部，要么是两个堆的顶部的平均值.

    Then, the median is the either the top of the larger heap, or the average of the tops of both heaps.

    如果您认为需要手动管理堆，则C++提供允许您对自己的随机访问数据结构进行管理的算法.

    If you feel you need to manage the heap manually, C++ provides algorithms that allow you to do so on your own random access data structure.

    • std::make_heap-堆化由迭代器端点指定的区域
    • std::push_heap-假设前N-1个元素已经是一个堆，并将第N个元素合并到该堆中
    • std::pop_heap-将区域中的第一个元素放到最后一个位置，并重新堆放区域，但最后一个元素留空
    • std::make_heap -- heapify a region specified by iterator endpoints
    • std::push_heap -- assumes the first N-1 elements are already a heap, and incoporates the N'th element into the heap
    • std::pop_heap -- places the first element in the region into the last position, and reheapifies the region, but leaving the last element alone

    这篇关于C ++实现堆中位数功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！