使用二进制堆的多个数组合并
给定k个整数的整数数组，每个整数包含一个未知的正数元素（每个数组中的元素数量不一定相同），其中所有k个数组中的元素总数为n，给出一个合并k个数组的算法单个排序数组，包含所有n个元素。 该算法的最坏情况时间复杂度应为O（n∙log k）。
将k排序的列表命名为1，…，k。
设A是组合排序数组的名称。
对于每个列表，我，从i中弹出v并将(i, v)推入最小堆。 现在，堆将包含每个列表中最小条目的值对和列表ID。
当堆不为空时，从堆中弹出(i, v)并将v附加到A 弹出列表i的下一个项目（如果它不是空的）并将其放入堆中。
堆中有n添加和删除。 堆在每个时间步骤最多包含k元素。 因此运行时为O(n log k) 。
也许只是不变量是堆包含未被清空的数组中的最小元素。 当您尝试从列表i中弹出一个项目时，如果此列表为空，则继续从堆中弹出元素。