Merge K Sorted Arrays

Given _k _sorted integer arrays, merge them into one sorted array.

Example

Given 3 sorted arrays:

[
  [1, 3, 5, 7],
  [2, 4, 6],
  [0, 8, 9, 10, 11]
]

return[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

Challenge

Do it in O(N log k).

• _N _is the total number of integers.

• _k _is the number of arrays.

K 路合并。可以用 heap，或者两两合并。用heap的方法：

    def mergekSortedArrays(self, arrays):
        import heapq
        minheap = []
        for i in xrange(len(arrays)):
            if arrays[i]:
                heapq.heappush(minheap, (arrays[i][0], i, 0) )

        result = []
        while minheap:
            num, i, j = heapq.heappop(minheap)
            result.append(num)
            # push next element if exists
            if j + 1 < len(arrays[i]):
                heapq.heappush(minheap, (arrays[i][j+1], i, j+1))

        return result