min-heapを使用してk個のソート済みリストをマージするアルゴリズムを証明する

Question

私はCLRSを読んでおり、エクササイズ6.5-8に問題がありました。

O（n個のLG k）を与えるkはマージする-timeアルゴリズムは、nが全ての入力 リスト内の要素の総数であるもの ソートリストにリストをソート。 （ヒント：Kウェイマージするmin0heapを使用する）誰もが言うよう

溶液は、k個のリストの最初の要素を使用して分ヒープK-要素を構築する）、

1であり、

2）抽出分（）は、ヒープから最小の要素を取得し、結果リストに追加し、

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

私は時間がO（n lg k）であることを理解することができますが、手順3）での選択の正しさは得られません。それはは明らかです明らかですが、いくつかの正式な証拠はありますか？

Answer 1

正当性証明の主な理由は、残っている要素が少ないことが常に抽出される要素であることです。この主張を支持する主要な不変な点は、優先度キューが、各リストについて、そのリストから残っている最小の要素を含むことである。この不変量から、残っている最小の要素も、そのリストの残りの要素のうち、最小のものがであるため、extract-minによって返されます。

パート3の同じリストから要素を選択して、各リストの要素がキューに入っていない不変量を維持する必要があります。私たちは1と3を含む最初のキューから1を引くと4に置き換える場合は、次の抽出が間違っている3を、する場所それ以外の場合、我々は

1 2 
3 4 

ような状況を持つことができます。