Каков оптимальный способ слияния списков k?

Question

Предположим, вам предоставлена ​​функция слияния, которая объединит (найдет объединение) два списка L1 и L2 размера s1 и s2 в O (s1 + s2). Каков оптимальный способ слияния k-списков размером s1, s2, ..., sk?

Я думаю, что мы должны сначала отсортировать s1, ..., sk и отсортировать первые два списка, которые соответствуют самым низким двум размерам. Когда они объединены, мы находим положение их размера в списке отсортированных размеров и продолжаем процесс до тех пор, пока не получим один список.

У меня возникли проблемы с двумя вещами: 1. действительно ли это оптимально (есть ли другой метод, который вернется быстрее)? 2. как мы анализируем время работы, когда размер списка изменяется при слиянии?

Answer 1

Это точно та же проблема, как найти оптимальную переменной длины битового кодирования для строки, образованной из алфавита k символов с известными частотами s1, s2, … sk. Ваш алгоритм - это точно Huffman algorithm, и вы найдете доказательство оптимальности в любом учебнике по алгоритмам (и многих онлайновых ресурсах), потому что это классический случай жадного алгоритма с простым доказательством корректности.

Повторное применение двухстороннего слияния индуцирует двоичное дерево, в котором каждый узел является слиянием. Учитывая это дерево, вклад любого листа в общую стоимость общего слияния - это вес этого листа, умноженный на его глубину в дереве. (Каждый узел является слиянием, а значения в листе участвуют точно в слияниях по пути от листа к корню, число таких слияний - это глубина листа в дереве.) Аналогично - или тождественно - -, общая длина битовой строки, кодированной Хаффманом, является суммой продуктов веса (частоты) символа с глубиной листа, соответствующей этому символу в дереве конструкции.

Небольшое усовершенствование вашего алгоритма (который часто пропускают люди, пишущие строители дерева Хаффмана): необходимо отсортировать весы s1, s2, … sk, но это единственный вид, который вам нужен. Оттуда алгоритм всегда выбирает два нижних узла и добавляет их. Полученные суммы должны быть монотонно неубывающими по размеру (если сумма меньше предыдущей суммы, предыдущая сумма не могла быть суммой двух наименьших элементов). Таким образом, вы можете поместить суммы в очередь; на каждом шаге вы выбираете два наименьших элемента из отсортированного массива листьев или (неявно) отсортированную очередь узлов.

Это может быть оптимизировано далее, переписывая массив листьев в очередь узлов. (Затем очередь растет со дна массива вверху, довольно просто доказать, что верхняя часть очереди никогда не догонит нижнюю часть массива.)