在O（logk）时间中删除K个排序的双链表的最小值

Question

因此，我正在尝试创建一种算法，用于从k个排序的双链表中删除最小值。在这里，我们有k个排序的双链表，其中n是所有列表中所有元素的总和。我们希望能够在O（logk）时间之内删除最小值，而仅花费O（n（k））时间来初始化数据结构。

我当时正在考虑创建一个最小堆，其中元素是每个列表的第一个元素（因此一次仅在堆中有k个元素），但是我不确定要从那里开始，特别是添加其余元素放入堆中。有人可以帮我这个忙吗？

Answer 1

根据我的理解（如果我错了，请纠正我），您有已排序的K双链表。您希望不断删除最小元素K次。每个删除必须在O（logK）中完成。

让我们举个例子：

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

您可以将每个列表的第一个元素及其所属的列表插入到最小堆中。

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(), 
  list: min_list
})
// new heap = [{key: 1, list: A}, {key: 2, list: B}]

现在您可以重复K次。从最小堆O（1）中弹出最小的元素，删除最小的元素O（1），将同一列表中的下一个元素添加回最小堆O（logK） 。