algorithm - 在 O(logk) 时间内删除 K 个排序的双向链表的最小值

Question

所以我试图创建一个算法来解决从 k 排序的双向链表中删除最小值的问题。在这里，我们有 k 个排序的双向链表，其中 n 是所有列表中所有元素的总和。我们希望能够在O(logk)时间内移除最小值，并且只需要O(n)时间来初始化数据结构。

我正在考虑创建一个最小堆，其中元素是每个列表的第一个元素（所以一次只有 k 个元素在堆中），但我不完全确定从那里去哪里，特别是添加其余的将元素放入堆中。谁能帮我解决这个问题？

标签： algorithmlinked-listheapdoubly-linked-listminimum

Answer 1

据我了解（如果我错了，请纠正我），您有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}

删除后，您必须将此列表中的下一个元素添加回最小堆（如果列表非空，则跳过此步骤）。

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)，将同一列表中的下一个元素添加回最小堆O(logK ) .