C ++ Implementing median heap function

Question

After the answer found here, https://stackoverflow.com/a/166268/212 , I am trying to implement two heaps to calculate the current median.

I am not familiar with heaps, and I do not know where to start this function described here. http://programmingpraxis.com/2012/05/29/streaming-median/

My goal is to create a small test program that effectively calculates the work of medians, as the list grows, the median does not require recounting from scratch. Using two heaps, I have to do this, I just stagger about how to start its implementation.

Any advice on this would be appreciated.

Answer 1

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

By default, priority_queue is the maximum 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 creating a mini-heap:

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

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

• create the maximum heap for items that are smaller than the median
• create a mini-heap for items that are larger than median
• when you click new items in a bunch
  • Decide which heap to insert and click there.
  • if one of the heap sizes is more than 1 larger than the other heap, then place the majority and place this element in a smaller

Then the median is either the top of the larger heap or the middle peak of both heaps.

If you think you need to manually manage the heap, C++ provides algorithms that let you do this in your own random access data structure.

• std::make_heap - heapify the region specified by the end points of the iterator
• std::push_heap - assumes that the first elements of N-1 are already a heap and add the Nth element to the heap
• std::pop_heap - puts the first element in the region at the last position and regenerates the region, but leaving only the last element

Answer 2

I think this will help. Thank you

  #include<cstdio> #include<iostream> #include<queue> #include <vector> #include <functional> typedef priority_queue<unsigned int> type_H_low; typedef priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int> > type_H_high; size_t signum(int left, int right) { if (left == right){ return 0; } return (left < right)?-1:1; } void get_median( unsigned int x_i, unsigned int &m, type_H_low *l, type_H_high *r) { switch (signum( l->size(), r->size() )) { case 1: // There are more elements in left (max) heap if (x_i < m) { r->push(l->top()); l->pop(); l->push(x_i); } else { r->push(x_i); } break; case 0: // The left and right heaps contain same number of elements if (x_i < m){ l->push(x_i); } else { r->push(x_i); } break; case -1: // There are more elements in right (min) heap if (x_i < m){ l->push(x_i); } else { l->push(r->top()); r->pop(); r->push(x_i); } break; } if (l->size() == r->size()){ m = l->top(); } else if (l->size() > r->size()){ m = l->top(); } else { m = r->top(); } return; } void print_median(vector<unsigned int> v) { unsigned int median = 0; long int sum = 0; type_H_low H_low; type_H_high H_high; for (vector<unsigned int>::iterator x_i = v.begin(); x_i != v.end(); x_i++) { get_median(*x_i, median, &H_low, &H_high); std::cout << median << std::endl; } }