докажете алгоритъма, който използва min-heap за обединяване на k сортирани списъка

Чета CLRS и имах проблем с упражнението 6.5-8.

Дайте алгоритъм за O(n lg k)-време за обединяване на k сортирани списъка в един сортиран списък, където n е общият брой елементи във всички списъци с входове. (Съвет: използвайте min0heap за k-way сливане.)

Решението е, както всички казват,

1) изградете k-елемент min-heap, като използвате първия елемент от k списъка,

2) extract-min(), за да получите най-малкия елемент от купчината и да го добавите към списъка с резултати,

3) изберете следващия елемент от същия списък като този, който току-що извлякохме от купчината. Поставете го в купчината и отидете на 2).

Мога да разбера, че времето е O(n lg k), но не разбирам правилността на избора в стъпка 3). Изглежда очевидно, но има ли официално доказателство?


algorithm min-heap
person jsz    schedule 02.05.2012    source източник
comment
Мисля, че вместо това сложността ще бъде O(k * n * lg k).   -  person jack_carver    schedule 30.11.2014

Отговори (1)


arrow_upward
8
arrow_downward

Основната идея на доказателството за коректност е, че най-малко оставащият елемент винаги е този, който трябва да бъде извлечен. Ключовият инвариант в подкрепа на това твърдение е, че приоритетната опашка съдържа, за всеки списък, най-малкото оставащ елемент от този списък. От този инвариант следва, че тъй като най-малко оставащ елемент е и най-малко оставащ елемент от неговия списък, той се връща от extract-min.

Трябва да изберем елемент от същия списък в част 3, за да поддържаме инварианта, че всеки списък има своя най-малък елемент в опашката. В противен случай може да имаме ситуация като

1 2
3 4

където, ако изтеглим 1 от първоначалната опашка, съдържаща 1 и 3, и го заменим с 4, следващото извличане ще бъде 3, което е грешно.

person root    schedule 02.05.2012
comment
Взех го благодаря. приоритетната опашка съдържа, за всеки списък, най-малкото останал елемент от този списък, това е ключът. - person jsz; 03.05.2012