6

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-andを見てみました-heap-sort/ヒープとヒープソートを理解するためですが、これは明確ではありませんでした。

max-heapify の機能がわかりません。再帰関数のように見えますが、どういうわけか、ツリーの高さのために対数時間で実行されると言われています。

私にはこれは意味がありません。最悪の場合、すべてのノードを逆にする必要はありませんか? すべてのノードに繰り返し触れずにこれを行う方法がわかりません。

4

3 に答える 3

8

MAX-HAPIFY の機能は次のとおりです。

左右のサブツリーが max-heap であるインデックスiのノードを指定すると、MAX-HAPIFY はiのノードをmax-heap プロパティに違反しなくなるまで (つまり、ノードが子供）。

ノードが適切な位置に移動するまでの最長パスは、ノードの開始時の高さと同じです。ノードがツリー内でもう 1 レベル下る必要があるたびに、アルゴリズムは取る分岐を 1 つだけ選択し、バックトラックすることはありません。ヒープ化されるノードが max-heap のルートである場合、ノードがたどることができる最長パスはツリーの高さ、つまりO(log n).

MAX-HEAPIFY は 1 つのノードのみを移動します。配列を最大ヒープに変換する場合は、ルートに移動する前に、すべてのサブツリーが最大ヒープであることを確認する必要があります。これを行うには、ノードで MAX-HAPIFY を呼び出しますn/2(リーフは常に max-heap プロパティを満たします)。

CLRS より:

for i = floor(length(A)/2) downto 1
   do MAX-HEAPIFY(A,i)

MAX-HAPIFYO(n)回呼び出すため、ヒープ全体の構築はO(n log n).*

* コメントで述べたように、 O(n)のより厳しい上限を示すことができます。分析については、 CLRSの第 2 版および第 3 版のセクション 6.3 を参照してください。(私の初版は梱包されているので、セクション番号を確認できませんでした。)

于 2016-01-28T03:32:16.073 に答える
3

最悪の場合、すべてのノードを逆にする必要はありませんか?

すべてのノードを通過する必要はありません。標準max-heapifyアルゴリズムは次のとおりです: (ウィキペディアから取得)

Max-Heapify (A, i):
    left ← 2*i  // ← means "assignment"
    right ← 2*i + 1
    largest ← i

    if left ≤ heap_length[A] and A[left] > A[largest] then:
        largest ← left
    if right ≤ heap_length[A] and A[right] > A[largest] then:
        largest ← right

    if largest ≠ i then:
        swap A[i] and A[largest]
    Max-Heapify(A, largest)

left再帰呼び出しごとに、サブツリーまたはを停止または続行することがわかりますright。後者の場合、 で木の高さを減らします1。ヒープ ツリーは定義上バランスがとれているため、ほとんどのlog(N)ステップで実行できます。

于 2016-01-28T01:35:27.010 に答える