问题描述：
问题来自习题6.5-8 给出一个时间为O(nlgk)，用来将k个已排序链表合并为一个排序链表的算法。 此处n为所有输入链表中元素的总数。（提示：用一个最小堆来做k路合并）。
在K路归并问题中，取出最小堆的根元素（最小元素）后，如果此元素没有后继元素（next为空）， 则有两种方案： 一、从K路中的另一个链表取出一个元素放到根位置。 二、将堆底部最后一个元素挪到根位置，并将堆大小减一。
此处采用方案二。堆大小每减一，说明K路中某一个链表已处理完。 当堆大小为零时，处理结束。
源码与注释：
// 链表结点类 class Node { int value; Node next;}
public class KMerge {
public static void main(String[] args) {
// 创建五路链表 LinkedList<Node> list1 = createList(2, 5, 8, 10); LinkedList<Node> list2 = createList(3, 4, 14); LinkedList<Node> list3 = createList(9, 11, 13, 15, 18); LinkedList<Node> list4 = createList(7, 12, 17, 22, 25); LinkedList<Node> list5 = createList(6, 16, 19, 21); LinkedList<LinkedList<Node>> kLists = new LinkedList<LinkedList<Node>>(); kLists.add(list1); kLists.add(list2); kLists.add(list3); kLists.add(list4); kLists.add(list5); // 开始归并 LinkedList<Node> resultList = kMerge(kLists); for (Node node : resultList) { System.out.print(node.value + ", "); } System.out.println(); } public static LinkedList<Node> kMerge(LinkedList<LinkedList<Node>> kLists) { int heapSize = kLists.size(); Node[] heap = new Node[heapSize + 1]; // 取出K路中每个链表的第一个元素，用来建堆。 for (int i = 1; i <= heapSize; i++) heap[i] = kLists.get(i - 1).getFirst(); buildMaxHeap(heap, heapSize); LinkedList<Node> resultList = new LinkedList<Node>(); while (heapSize > 0) {
// 将根位置的最小元素取出到结果中。 Node minNode = heap[1]; resultList.add(minNode);
// 后继为空，则将堆尾元素挪到根位置。 // 否则将后继元素添加到堆中。 if (minNode.next == null) { heap[1] = heap[heapSize]; heapSize -= 1; } else { heap[1] = minNode.next; }
// 根位置的堆性质被破坏，重新恢复。 minHeapify(heap, heapSize, 1); } return resultList; }
public static void buildMaxHeap(Node[] heap, int heapSize) { for (int i = heapSize / 2; i >= 1; i--) minHeapify(heap, heapSize, i); } public static void minHeapify(Node[] heap, int heapSize, int i) { int left = 2 * i; int right = 2 * i + 1; int min = i; if (left <= heapSize && heap[left].value < heap[i].value) min = left; if (right <= heapSize && heap[right].value < heap[min].value) min = right; if (min != i) { Node tmp = heap[i]; heap[i] = heap[min]; heap[min] = tmp; minHeapify(heap, heapSize, min); } } public static LinkedList<Node> createList(int... values) { LinkedList<Node> list = new LinkedList<Node>(); Node preNode = null; for (int value : values) { Node node = new Node(); node.value = value; if (preNode != null) preNode.next = node; list.add(node); preNode = node; } return list; } }
效率分析：
堆的大小为K，调用buildMaxHeap()建堆花费KlgK。剩余元素为N - K个。 每次取出根元素，放入后继元素后，调用maxHeapify()保持堆性质花费lgK。 所以总的时间为KlgK + (N - K)lgK = NlgK。