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

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

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

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

1) построить k-элементную min-кучу, используя первый элемент k списков,

2 ) Extract-min(), чтобы получить наименьший элемент из кучи и добавить его в список результатов,

3) выбрать следующий элемент из того же списка, что и тот, который мы только что извлекли из кучи . Вставьте его в кучу и перейдите к 2).

Я понимаю, что время равно O(n lg k), но не понимаю правильности выбора на шаге 3). Это кажетсяочевидным, но есть ли какие-то формальные доказательства?