用最小堆将k个已排序链表合并为一个排序链表

时间:2021-08-21 09:51:44

问题:请给出一个时间为O(nlgk),用来将k个已排序链表合并为一个排序链表的算法。此处的n为所有输入链表中元素的总数。

编程思路:

假设k个链表都是非降序排列的。

(1)取k个元素建立最小堆,这k个元素分别是k个链表的第一个元素。建堆的时间复杂度O(k)。

(2)堆顶元素就是k个链表中最小的那个元素,取出它。时间复杂度O(1)。

(3)若堆顶元素所在链表不为空,则取下一个元素放到堆顶位置,这可能破坏了最小堆性质,所以进行堆调整。堆调整时间复杂度O(lgk)。若为空,则此子链表已经被合并完毕,则删除最小堆的堆顶元素,此时最小堆的heapSize减小了1 。删除指定元素时间复杂度O(lgk)。

(4)重复步骤(2)~(3)n-k次。总的时间复杂度是O(k)+O(nlgk)即O(nlgk)。