算法导论 6.5.9 堆实现K路归并问题

时间:2023-03-08 17:25:16
算法导论 6.5.9 堆实现K路归并问题

问题: 设计一个时间复杂度为O(NlogK)的算法,它能够将K个有序链表合并为一个有序链表,这里的N为所有输入链表包含的总的元素个数

分析:

该问题为经典的利用堆完成K路归并的问题:

当K个序列满足一定的条件(如单调不减或单调不增)时,利用堆实现K路归并使其归并为一个满足相同条件的

序列,具体做法如下:

1)假设存在K个序列,从每一个序列中取出一个元素放于堆中;

2)从堆中取出顶端元素,并在该元素的序列中取出下一个元素插入堆中。

3)重复操作1)与2),直到完成归并。

具体问题: poj_2051