堆实现多路合并
16 January 2013
给定k个已排序链表,将其合并为一个有序链表。n为所有链表元素的总数。
思路:
利用最小堆进行k路合并。
- 以链表的第一个元素为key将所有链表组织成k个元素的最小堆
- 取出堆顶链表的第一个元素,并将其第二个元素作为key
- 保持堆的性质,调整堆
- 重复2、3直到堆为空
此算法时间复杂度为O(nlgn)
blog comments powered by Disqus
给定k个已排序链表,将其合并为一个有序链表。n为所有链表元素的总数。
思路:
利用最小堆进行k路合并。
此算法时间复杂度为O(nlgn)