udowodnić algorytm, który używa min-sterty do scalania sortowanych list k

Question

Czytam CLRS i miał jakiś problem z ćwiczeniem 6.5-8.

Podaj O (N lg k) -czas algorytm do połączenia k klasyfikowane wykazy do jednego posortowanej listy, gdzie n jest całkowitą liczbą elementów na wszystkich wejściach list. (Wskazówka: użyć min0heap K-way łączenia).

Roztwór, a każdy mówi

1) opiera się na k-element min sterty pomocą pierwszego elementu list k

2) ekstraktu min(), aby najmniejszy element ze sterty i dołączyć je do listy wynikowej

3) odebrać następny element z samej listy jak ten właśnie pochodzących kupa. Włóż go do sterty i goto 2).

Mogę zrozumieć, że czas jest O (n lg k), ale nie otrzymuję poprawności wyboru w kroku 3). Wygląda na to, że jest, ale czy istnieje jakiś dowód formalny?

Answer 1

Głównym ciągiem dowodu poprawności jest to, że najmniejszy pozostały element jest zawsze tym, który ma zostać wyodrębniony. Kluczowym niezmiennikiem na poparcie tego twierdzenia jest to, że kolejka priorytetowa zawiera, dla każdej listy, najmniejszy element pozostały z tej listy. Z tego niezmiennika wynika, że ​​ponieważ najmniejszy element pozostały jest również najmniejszym elementem pozostającym na liście z listy, jest zwracany przez extract-min.

Musimy wybrać element z tej samej listy w części 3, aby zachować niezmienność, że każda lista ma najmniejszy element w kolejce. W przeciwnym razie możemy mieć sytuację jak

1 2 
3 4 

gdzie jeśli będziemy ciągnąć 1 z początkowej kolejki zawierający 1 i 3 oraz zastąpienie go 4, obok wydobycie wyniesie 3, co jest nie tak.