доказать алгоритм, использующий min-heap для слияния k отсортированных списков

Я читаю CLRS и у меня возникла проблема с упражнением 6.5-8.

Предложите алгоритм за O(n lg k) для объединения k отсортированных списков в один отсортированный список, где n — общее количество элементов во всех входных списках. (Подсказка: используйте min0heap для слияния k-way.)

Решение, как все говорят,

1) построить k-элементную мини-кучу, используя первый элемент 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