合并k个有序数组

有K个长度不定的有序数组，将这些数组合并为一个有序数组。

示例：

输入： [1, 3, 5, 7], [2, 4, 6, 7], [3, 5, 6], [2], [1]

输出：[1 2 2 3 3 4 5 5 6 6]

解题思路：利用最小堆求最小值

1. 初始化一个最小度，其中最小度的元素为k；

2. 遍历数组获取第一个元素插入到最小堆中，同时记录元素在那个数组中的那个位置；

3. 删除最小堆中的最小值，并获取该数组中的下一个元素插入到堆中，如果该数组已经处理完成，则继续获取下一个元素，循环直至最小堆的元素为空；

package main

import (
	"fmt"
	"errors"
)

type ele struct {
	v int
	index int
	kindex int
}

type minHeap struct {
	size int
	eles []*ele
}

func (m *minHeap) delEle() (*ele, error) {
	if len(m.eles) <= 0 {
		return nil, errors.New("minHeap empty")
	}
	ret := m.eles[0]
	x := m.eles[m.size]

	i := 0
	for {
		l := 2*i + 1
		r := 2*i + 2

		if l >= m.size {
			break
		}

		if r < m.size && m.eles[l].v > m.eles[r].v {
			l = r
		}
		if x.v <= m.eles[l].v {
			break
		}
		m.eles[i] = m.eles[l]
		i = l
	}
	m.size--
	m.eles[i] = x
	
	return ret, nil
}

func (m *minHeap) insEle(e *ele) {
	m.size++
	i := m.size
	for i > 0 {
		parent := (i - 1) / 2
		if m.eles[parent].v <= e.v {
			break
		}
		m.eles[i] = m.eles[parent]
		i = parent
	}
	m.eles[i] = e
}

func (m *minHeap) length() int {
	return m.size
}

func mergeArr(params ...[]int) []int {
	k := len(params)
	res := []int{}

	min := &minHeap{
		eles: make([]*ele, k),
		size: -1,
	}

	// 获取数组的第一个元素插入到最小堆中
	for j := 0; j < k; j++ {
		 if len(params) >= 1 {
			min.insEle(&ele{
				v: params[j][0],
				index: 0,
				kindex: j,
			})
		 }
	}

	for min.length() > 0 {
		e, _ := min.delEle()
		res = append(res, e.v)

		if len(params[e.kindex]) - 1 > e.index {
			min.insEle(&ele{
				v: params[e.kindex][e.index + 1],
				index: e.index + 1,
				kindex: e.kindex,
			})
		}
	}

	return res
}

func main() {
	fmt.Println(mergeArr([]int{1, 3, 5, 7}, []int{2, 4, 6, 7}, []int{3, 5, 6}, []int{2}, []int{1}))
}