2

最小-最大ヒープは、 で最小要素と最大要素の両方を見つけ、 でO(1) それを削除できるヒープですO(log n)。これは従来のヒープと密接に関連していますが、実際には 3 つのヒープ (最小ヒープと 2 つの最大ヒープ) をインターリーブします。ここで、偶数レベルは最小レベルで、奇数レベルは最大レベルです (つまり、2 つのルートがあります)。従来のヒープ プロパティは、子ではなく孫に関して保持されます。min-max-heap のリーフ レベルは、基本的に min ヒープと max ヒープの間で共有されます。ここに挿入された新しい要素は、ツリーの偶数レベルまたは奇数レベルの両方に移動できます。

シフトアップとシフトダウンは単純な変更ですが、トリッキーな部分は、要素をヒープの最小順序部分から最大順序部分に移動する必要がある場合です。

従来のヒープの場合、ボトムアップ ヒープ修復を実行することでツリーを一括読み込みできますがO(n)、明らかに 1 つずつ挿入するには時間がかかりO(n log n)ます。一括挿入でもこれを行うことができます。1 つずつ挿入する代わりに、すべてを追加してヒープを一括修復できます。

最小最大ヒープの場合、もちろん線形にロードできますが、ヒープをボトムアップO(n log n)で一括ロードまたは一括修復する方法もあるのだろうか?O(n)

4

2 に答える 2

2

同じ質問をしている可能性のある他の人のために、これまでに見つけたことで自分自身に答えます。

最小/最大ヒープは、基本的に3 つのヒープを 1 つにまとめたもので、リーフ レベルを共有します。

       min1           <--- one min heap, first level
     /      \
   mi2       mi3      <--- third level
  /   \     /   \
 m5   m6   m7   m8    <--- fifth level
 /\   /\   /\   /\
a  b c  d e  f g  h   <--- leaf level (here: sixth level)
 \/   \/   \/   \/
 x1   x2   x3   x4    <--- fourth level
   \ /       \ /
   max1      max2     <--- two max heaps, second level

(重要な注意: ヒープのファンアウトは 4 であるため、これは正確ではありません! さらに、これは論理的な順序であり、ヒープをレベルごとにインターリーブするメモリ レイアウトではありません) リーフ レベルのオブジェクトはすべてに属します。 3 つのヒープ。これは要素がヒープの最小部分から最大部分に移行する場所です。

これで、最小ヒープと最大ヒープのサイズを計算し、quickselect などの部分的な並べ替えを使用してデータを分割し、3 つの部分を個別に一括読み込みできます。ただし、quickselect は、一括読み込み全体(データ セットの部分的な順序付け)と同じくらいコストがかかります。ヒープの一括読み込みと一括修復 (!) のもう 1 つの明白な方法は、より小さなサブヒープを調べることです。通常の最小ヒープでは、a、b、c の 3 つの要素のアトミック ヒープを見て、a が最小であることを確認します。ここでは、高さ 4、つまり 15 要素のヒープを見ることができます。

         min1
         /  \
    max1      max2
   /  \        /  \
 m1    m2    m3    m4
 /\    /\    /\    /\
a  b  c  d  e  f  g  h

そして、min1 が最小、max1 と max2 が 2 つの最大値、m1-m4 が次の 4 つの最大値であることを確認し、2 つのレベルのステップでツリーを登ります (つまり、最小レベルのみ)。

または、サイズ 7 (3 レベル) のヒープを見て、最小タイプと最大タイプを識別することができます

   min1           max1
   /  \           /  \
max1  max2     min1  min2
 /\    /\       /\    /\
a  b  c  d     a  b  c  d

最小レベルには最初のタイプがあり、最大レベルには 2 番目のタイプがあることを確認します。次に、すべてのレベルを通過する必要があります。

しかし、さらに優れた解決策は、interval heapsを使用することです。これも本質的に、インターリーブされた最小ヒープと最大ヒープです。ただし、それらは対称的にインターリーブされ、同じサイズです。それらは実装がはるかに簡単なようで、次のようなヒープとして解釈できます。

      min1,max1
      /       \
min2,max2   min3,max3

一括読み込みの詳細については、元のインターバル ヒープの出版物を参照してください。

したがって、一括読み込み可能な min-max-heap に興味がある場合は、代わりにインターバル ヒープを検討することを検討してください。とにかく、最小最大ヒープよりも優れていると言う人もいます。それらは密接に関連しており、実装がより簡単になるはずです。特に、min-max-heap のパフォーマンスが向上する明確な理由はありません。詳細な複雑さの分析により、必要な比較とスワップの一定の要因によってパフォーマンスが低下することが示されても、私は驚かないでしょう (私が知る限り、ヒープの正しさを検証するために、min-max-heap ではより多くの比較が必要であることが単純にわかります)。

于 2012-07-29T16:44:15.750 に答える
0

ボトムアップのツリー修復が機能するはずです。

def heapify(N)
  if (N is a min-node)
     if(*N > *left_child(N))
        swap(*N, *left_child(N))
     if(*N > right_child(N))
        swap(*N, *right_child(N))
     find the smallest X among N, grand-children(N)
  else
     if(*N < left_child(N))
        swap(*N, *left_child(N))
     if(*N < right_child(N))
        swap(*N, *right_child(N))
     find the largest X among N, grand-children(N)
  if(X != N)
     swap(*X, *N)
     heapify(X)

load heap in arbitrary order
for each N in bottom-up order of heap
   heapify(N)
于 2012-07-25T10:37:31.317 に答える