10

CLRSを読んでいて、6.5-8の演習で問題が発生しました。

O（n lg k）時間アルゴリズムを指定して、k個のソート済みリストを1つのソート済みリストにマージします。ここで、nはすべての入力リストの要素の総数です。（ヒント：k-wayマージにはmin0heapを使用してください。）

解決策は、誰もが言うように、

1）kリストの最初の要素を使用してk要素の最小ヒープを構築します。

2）extract-min（）を使用してヒープから最小の要素を取得し、結果リストに追加します。

3）ヒープから抽出したものと同じリストから次の要素を選択します。それをヒープに挿入し、2）に進みます。

時間はO（n lg k）であることは理解できますが、ステップ3）での選択の正しさはわかりません。当たり前のようですが、正式な証明はありますか？

4

1 に答える 1

8

正しさの証明の主な目的は、残っている最小の要素が常に抽出される要素であるということです。この主張を裏付ける重要な不変条件は、優先度付きキューに、リストごとに、そのリストから残っている最小の要素が含まれていることです。この不変条件から、残りの最小要素はリストから残っている最小要素でもあるため、extract-minによって返されます。

パート3の同じリストから要素を選択して、各リストのキュー内の要素が最小であるという不変条件を維持する必要があります。そうでなければ、私たちは次のような状況になる可能性があります

1 2
3 4

ここで、1と3を含む最初のキューから1をプルし、それを4に置き換えると、次の抽出は3になりますが、これは誤りです。

于 2012-05-02T13:20:19.937 に答える