问题: 设计一个时间复杂度为O(NlogK)的算法,它能够将K个有序链表合并为一个有序链表,这里的N为所有输入链表包含的总的元素个数
分析:
该问题为经典的利用堆完成K路归并的问题:
当K个序列满足一定的条件(如单调不减或单调不增)时,利用堆实现K路归并使其归并为一个满足相同条件的
序列,具体做法如下:
1)假设存在K个序列,从每一个序列中取出一个元素放于堆中;
2)从堆中取出顶端元素,并在该元素的序列中取出下一个元素插入堆中。
3)重复操作1)与2),直到完成归并。
具体问题: poj_2051