16 January 2013

给定k个已排序链表,将其合并为一个有序链表。n为所有链表元素的总数。
思路:
利用最小堆进行k路合并。

  1. 以链表的第一个元素为key将所有链表组织成k个元素的最小堆
  2. 取出堆顶链表的第一个元素,并将其第二个元素作为key
  3. 保持堆的性质,调整堆
  4. 重复2、3直到堆为空

此算法时间复杂度为O(nlgn)



blog comments powered by Disqus