0

maxheapとminheapがあり、maxheapの最大要素がminheapの最小要素以下です。

ここで、minheapの最小要素を移動して、maxheapの最大要素にします。

これを行う1つの方法は、minheapの一番上の要素をポップし、それをmaxheapにプッシュすることです。

これを行うためのより効率的な方法はありますか？

これが私がやったことです：

私は実際に要素をminheapに挿入してから、上記の操作を実行する必要がありました。次のようにしました。

// place value to insert at end of minheap
mintoph[mintoph_size] = R;

// use std::pop_heap, minimum element now at end
pop_heap(mintoph.begin(), mintoph.begin() + mintoph_size + 1, greater<int>());

// (*) make room in maxheap at top
for (int pos = maxboth_size++; pos > 0;)
{
    int parent = (pos - 1) / 2;
    maxboth[pos] = maxboth[parent];
    pos = parent;
}

// move element from back of minheap to maxheap head
maxboth[0] = mintoph[mintoph_size];

親が子供に降格されるため、上記のステップですでに支払われた比較の無駄がありますが、(*)これは避けられないと思います。

4

3 に答える 3

2

本当に必要なのは、挿入される要素が最小ヒープか最大ヒープかに応じて、最小/最大よりも小さい/大きいことがわかっている場合に、優先キューに挿入する効率的な方法です。従来の「ヒープ」データ構造の場合、これにはO（log n）時間がかかります。

ただし、優先キューに従来の「ヒープ」データ構造とは異なる表現を使用する場合は、そのような挿入をO（1）時間で簡単に実行できます。左翼ヒープ、スキューヒープ、ペアリングヒープなど、さまざまな種類の優先度キューでこれを実行できます。

編集：もちろん、元の優先キューから削除するコストを支払う必要があります。これは、とにかくO（log n）になる可能性がありますが、「遅延削除」など、そこでも役立つ可能性のあるアプローチがあります。 。

于 2012-07-07T22:09:13.377 に答える
0

おそらく、min-max-heapまたはtreapを使用するのが最適です。min-max-heapはあなたがしていることに合わせて作られたように見えますが、treapは非常にバランスが取れているので、うまく機能する可能性があります。特に、最小値と最大値を調べて値を追加するだけでは不十分な場合はなおさらです。

http://en.wikipedia.org/wiki/Min-max_heap

http://en.wikipedia.org/wiki/Treap

于 2012-07-06T23:05:48.220 に答える
-1

min-maxヒープを使用します。これは両端優先キューです。これはo（lgn）で実行できますが、O（lgn）未満では実行できません。

ただし、フィボナッチヒープのようにo（1）に挿入する償却アルゴリズムを使用できます。

于 2012-07-06T19:25:24.937 に答える