Убрать мин для K отсортированных двусвязных списков за время O (logk)

Question

Поэтому я пытаюсь создать алгоритм для задачи удаления минимума из k отсортированных двусвязных списков. Здесь мы отсортировали двусвязные списки, где n - сумма всех элементов во всех списках. Мы хотим иметь возможность удалить минимум в течение O (logk) времени и только O (n) времени для инициализации структура данных.

Я думал о создании минимальной кучи, где элементы являются первым элементом каждого списка (поэтому только k элементов в куче за раз), но я не совсем уверен, откуда go из там, в частности, с добавлением остальных элементов в кучу. Может ли кто-нибудь помочь мне с этим?

Answer 1

Из того, что я понимаю (пожалуйста, поправьте меня, если я ошибаюсь), у вас есть K двусвязные списки, которые отсортированы. Вы хотите продолжать удалять самый маленький элемент. Каждое удаление должно быть сделано в O (logK) .

Давайте рассмотрим пример:

A = {1, 1, 2, 3}
B = {2, 3, 4, 5}

Вы можете вставить первый элемент каждого списка вместе с тем списком, которому он принадлежит, в min-heap.

heap = [{key: 1, list: A}, {key: 2, list: B}]

Затем вы можете вытолкнуть наименьший элемент из минимальной кучи. Теперь вы можете удалить этот элемент.

min_val = heap.pop()     // {key: 1, list: A}
min_list = min_val.list  // list = A
min_list.delete_first()  // new A = {1, 2, 3}

После удаления вы должны добавить следующий элемент из этого списка обратно в min-heap (если список не пуст, иначе пропустите этот шаг).

heap.add({ 
  key: min_list.fist_element(), // key: 1
  list: min_list                // list: A
})
// new heap = [{key: 1, list: A}, {key: 2, list: B}]

Теперь вы можете повторять это для каждой операции удаления. Выдвиньте наименьшее из минимальной кучи O (1) , удалите наименьший элемент (т.е. первый элемент из двусвязного списка) O (1) , добавьте следующий элемент из тот же список обратно в min-heap O (logK) .

Answer 2

У вас есть k списков, и все они имеют сумму n , поэтому каждый список должен иметь среднюю сумму a = n / k .

Секретный вопрос: как долго вам нужно перебирать список, чтобы выяснить, что сумма не меньше a ?

Например, предположим, a = 10 и ваш список [5, 6, 7]. Просто взглянув на первый элемент (и зная длину списка), вы узнаете, что сумма списка больше средней, поэтому вы можете полностью ее игнорировать. По сути, для каждого элемента Li, который вы читаете из списка L, вы можете спросить, если

L1 + L2 + ... + Li + (Li * (s - i)) >= n/k

, где s - длина списка. Пока вам нужно читать списки, это не будет стоить вам дополнительного времени и сократит примерно половину списков.