# go 优先队列
## 优先队列
优先队列的底层是堆排序，堆排序在之前实现过，[go堆排序](https://studygolang.com/articles/35298)。
优先队列也是有pop&push两个功能，在pop时会取出堆里的最大/小值，push时会对内部的数据重新排序，本质上就是堆排序，当我想自己实现优先队列时，发现官方 ‘container/heap’这个标准库，决定就以这个heap库来实现优先队列，并用来解决leetCode23题
## 题解分析
和合并2个链表没区别，当k=2时就是合并2个链表
## CODE
```go
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
}
```
有疑问加站长微信联系（非本文作者））
