2

バイナリの最大ヒープ (一番上に最大の要素) があり、 20 個の要素に到達するたびに最小の要素を削除して、一定のサイズ (たとえば 20 個の要素) に保つ必要があります。バイナリ ヒープは配列に格納され、ノード i の子は 2*i および 2*i+1 (i はゼロ ベース) にあります。任意の時点で、ヒープには 0 から 20 までの 'n_elements' 要素があります。たとえば、配列 [16,14,10,8,7,9,3,2,4] は有効な最大バイナリ ヒープになります。 16 には 14 と 10 の子供がいて、14 には 8 と 7 の子供がいます ...

最小の要素を見つけるには、一般に、n_elements/2 から n_elements まで配列をトラバースする必要があるようです。最小の要素が配列の最後の要素であるとは限りません。

したがって、その配列だけでは、最小のeltを見つけて削除しようとする試みは少なくともO(n)のようです。あれは正しいですか？

4

3 に答える 3

5

特定の有効な最大ヒープでは、最小値はリーフ ノードのみになります。次の質問は、配列内のヒープのリーフ ノードを見つける方法です。配列の最後のノードを注意深く観察すると、それは最後のリーフ ノードになります。式で葉ノードの親を取得する

parent node index = (leaf Node Index)/2

インデックスから最後のリーフ ノード インデックスまで線形検索を開始(parent node index +1)し、その範囲の最小値を取得します。

FindMinInMaxHeap(Heap heap)
   startIndex = heap->Array[heap->lastIndex/2]
   if startIndex == 0
          return heap->Array[startIndex]
   Minimum = heap->Array[startIndex + 1]
   for count from startIndex+2 to heap->lastIndex
            if(heap->Array[count] < Minimum)
                Minimum := heap->Array[count]
   print Minimum
于 2013-03-10T14:22:28.063 に答える
3

O(n)ヒープのみを使用して、最大ヒープから最小の要素を見つけて削除するパフォーマンスを向上させる方法は考えられません。あなたが取ることができる1つのアプローチは次のとおりです。

このヒープ データ構造を自分で作成している場合は、配列内の最小要素の位置への別のポインターを保持できます。そのため、新しい要素がヒープに追加されるたびに、新しい要素が小さいかどうかを確認してください。はいの場合は、ポインターなどを更新します。次に、最小の要素を見つけることはO(1).

MBo は、各削除後に次に小さい要素を取得する方法についてのコメントで良い点を挙げています。削除するたびに、次に小さい要素を見つけるために O(n) を実行する必要があります。したがって、除去は依然としてO(n). しかし、最小の要素を見つけることはO(1)

より高速な削除も必要な場合は、すべての要素の最小ヒープも維持する必要があります。その場合、削除はO(log(n)). 2 つのヒープに挿入する必要があり、2 倍のスペースも必要であるため、挿入には 2 倍の時間がかかります。

ちなみに、ある時点で 20 個の要素しかない場合、これはあまり問題にはなりません (宿題の問題であるか、単に楽しみのためにやっている場合を除きます)。数千の値にスケーリングする場合にのみ、それは本当に重要です。

于 2012-05-29T20:19:49.343 に答える
0

minmaxヒープデータ構造があります：http：//en.wikipedia.org/wiki/Min-max_heap。もちろん、コードはかなり複雑ですが、2つの別々のヒープがある場合は、多くの追加スペースを使用し（2番目のヒープ用、1対1のマッピングを維持するため）、ジョブを2回実行する必要があります。

于 2012-05-30T11:03:44.813 に答える