C ++ реализует функцию медианы кучи
После ответа, найденного здесь,https://stackoverflow.com/a/10931091/1311773Я пытаюсь реализовать две кучи, чтобы я мог рассчитать текущую медиану.
Я не знаком с кучами и не уверен, с чего начать реализацию этой функции, описанной здесь.http://programmingpraxis.com/2012/05/29/streaming-median/
Моя цель состоит в том, чтобы создать небольшую тестовую программу, которая бы эффективно рассчитывала текущие медианы, так что по мере роста списка медиана не нуждается в пересчете с нуля. Используя две кучи, я должен быть в состоянии сделать это, я просто шокирован тем, как начать это реализовывать.
Любые советы по этому вопросу будут оценены.
Ответы на вопрос(2)
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>
>;
Для реализации алгоритма медианного потока подход подобен следующему:
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Тогда медиана - это либо вершина большей кучи, либо среднее значение вершин обеих куч.
Если вы чувствуете, что вам нужно управлять кучей вручную,C++ предоставляет алгоритмы, которые позволяют вам делать это на вашей собственной структуре данных произвольного доступа.
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
#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;
}
}