6

私はこれを数日間理解しようとしています。私は次のように言う学校の問題を抱えています：

Aを最小ヒープとします。操作HEAP-MODIFY（A、i、k）は、ノードiのキーを新しい値kに変更してから、最小ヒープ内の要素を再配置します。n要素の最小ヒープに対してO（lgn）時間で実行されるHEAPMODIFYの実装を提供します。

O（lg（n））時間で実行されるアルゴリズムを設計する必要があるため、各要素を反復処理するだけでは不十分であることがわかります。私は次の解決策を持っていますが、それが正しいかどうかはわかりません。

HEAP-MODIFY(A,i,k):
    A[i] = K

    if A[i] < A[i/2]
        while A[i] < A[i/2] and i > 1
            exchange A[i], A[i/2]
            i=i/2
    else if A[i] > A[2*i]
    while A[i] > A[2*1] and i <k
        exchange A[i], A[2*i]
        i = 2*1

これにどのように取り組むことができるかについての提案はありますか？

4

3 に答える 3

3

あなたは正しい方向に考えていますが、実行する操作は結果として最小ヒープを保証しません。次のヒープを見てください。

  ..
  11
 /  \
19  63 (<-was 13)
.. /  \
  55  15
  ..  ..

キー13を63に更新したばかりで、min-heapプロパティを復元したいとします。55 <63であるため、コードは55と63を交換しますが、55よりも63と15（！）の親になるため、min-heapプロパティが損なわれます。

（min-heapプロパティを復元するために）必要な関数は「heapify」と呼ばれます。些細なことではありませんが、それほど複雑でもありません。ヒープソートに関するこのウィキペディアの記事でその説明を調べてください。ソリューションをコピーするだけでなく、理解している限り、ソリューションを読んだり学習したりするだけでも問題はありません。

それでも質問がある場合は、質問してください。

于 2011-02-22T02:06:55.920 に答える
3

Node（i）を見つけて削除し、Nodeの値をkに変更して、ヒープに戻すことができます。これは最も効率的な方法ではありませんが、それでもlog（n）です。利点は、シンプルで、すでに実装した操作を再利用できる可能性が高いことです。

于 2011-02-22T02:19:54.233 に答える
1 
HEAP-MODIFY(A,i,K) 
A[i] = K 
MIN-HEAPIFY(A,1)

私もこの問題に取り組んでいて、これを手に入れました。私はあなたと同じように混乱していますが、あなたのコードは上でそれを過度に複雑にしているように感じます。

于 2011-02-22T02:29:52.987 に答える