go 优先队列

优先队列

优先队列的底层是堆排序，堆排序在之前实现过，go堆排序。

优先队列也是有pop&push两个功能，在pop时会取出堆里的最大/小值，push时会对内部的数据重新排序，本质上就是堆排序，当我想自己实现优先队列时，发现官方 ‘container/heap’这个标准库，决定就以这个heap库来实现优先队列，并用来解决leetCode23题

题解分析

和合并2个链表没区别，当k=2时就是合并2个链表

CODE

type Item struct {
    value    *ListNode
    priority int
    index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = j
    pq[j].index = i
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    item.index -= 1
    *pq = old[0 : n-1]
    return item
}
func mergeKLists(lists []*ListNode) *ListNode {
    // 处理边界
    length := len(lists)
    if length < 1 {
        return nil
    }
    if length == 1 {
        return lists[0]
    }

    truLength := 0
    for _, v := range lists {
        if v != nil {
            truLength ++
        }
    }
    if truLength == 0 {
        return nil
    }

    dummy := &ListNode{}
    current := dummy
   // 初始化队列
    pq := make(PriorityQueue, truLength)

    index := 0
    for _, v := range lists {
        if v != nil {
            pq[index] = &Item{
                value: v,
                priority: v.Val,
                index: index,
            }
            index ++
        }
    }
    // 堆排序
    heap.Init(&pq)

    for pq.Len() > 0 {
        // 出队
        item := heap.Pop(&pq).(*Item)
        curNode := item.value
        current.Next = curNode
        current = current.Next
        if curNode.Next != nil {
            newItem := &Item{
                value: curNode.Next,
                priority: curNode.Next.Val,
            }
            // 入队
            heap.Push(&pq, newItem)
        }
    }

    return dummy.Next

}