4

https://stackoverflow.com/a/10931091/1311773にある回答に従って、実行中の中央値を計算できるように 2 つのヒープを実装しようとしています。

私はヒープに不慣れで、ここで説明されているこの関数の実装をどこから始めればよいかわかりません。http://programmingpraxis.com/2012/05/29/streaming-median/

私の目標は、実行中の中央値を効率的に計算する小さなテスト プログラムを作成して、リストが大きくなっても中央値を最初から再計算する必要がないようにすることです。2つのヒープを使用して、私はそれを行うことができるはずです.私はそれを実装する方法に不安があります.

これに関するアドバイスをいただければ幸いです。

4

2 に答える 2

4

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つが他のヒープより1より大きい場合は、大きい方のヒープをポップし、その要素を小さい方のヒープに配置します。

次に、中央値は、大きい方のヒープのトップ、または両方のヒープのトップの平均のいずれかです。

ヒープを手動で管理する必要があると思われる場合はC++、独自のランダムアクセスデータ構造で管理できるアルゴリズムを提供します。

  • std::make_heap--イテレータエンドポイントによって指定された領域をヒープ化します
  • std::push_heap--最初のN-1要素がすでにヒープであると想定し、N番目の要素をヒープに組み込みます
  • std::pop_heap -領域の最初の要素を最後の位置に配置し、領域を再ヒープしますが、最後の要素はそのままにします
于 2012-06-10T04:30:07.070 に答える