# 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**](http://www.lintcode.com/en/problem/merge-k-sorted-arrays/#challenge)
>
> Do it in O(N log k).
>
> * \_N \_is the total number of integers.
> * \_k \_is the number of arrays.

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

```python
    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
```