1

(USC CSCI 303 宿題 4) 問題 7 (6.5-7):

この操作は、 node の項目をheap からHeap-Delete(A, i)削除します。n要素の最大ヒープに対してO ( lg n ) 時間で実行される の実装を与えてください。iAHeap-Delete

参照ソリューションの疑似コードと説明は次のとおりです。

Heap-Delete(A, i)
    A[i] ↔ A[length(A)] 
    length(A) ← length(A) - 1
    Heapify(A, i)

アルゴリズムは node の要素を削除iし、最後の要素に置き換えます。次に、アルゴリズムHeapifyはノードから実行されますi。

「↔」は「←」の方がいいのではないですか？またはこれは本当に必要ですか？

これは http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf (ページ 4)から入手しました。

4

3 に答える 3

2

それは本当に必要ではありません。おそらく、意図はその要素を返すことです。その場合、上書きされる前にどこかに保存する必要があります。

于 2013-03-15T09:56:19.740 に答える
0

おそらくこれはHeap-Delete()、ヒープソートの実行中に を繰り返し呼び出すことができるようにするためです。ヒープソートでは、最大のアイテムがヒープから取り出され、ヒープの最後のアイテムに隠され、ヒープ サイズが 1 減ります。次に、ヒープが再ヒープ化され、次に大きなアイテムに進みます。ヒープのサイズが 1 の場合の最終結果は、ヒープの基になっている/元だった配列が最小から最大の順に並べ替えられることです。Heap-Delete()このように書くと、Heap-Sort()非常に簡単になります。

while (HeapSize>0)
   HeapDelete(0)

これは、私の理論に反する証拠かもしれませんHeap-Delete()。lengthしかし、とにかくこれは私の最善の推測です。

于 2013-03-15T16:45:27.363 に答える