使用container/heap实现一个简单的优先级队列.
package main
import (
"container/heap"
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
// 定义一个优先级队列
type PriorityQueue []*ListNode
func (p PriorityQueue) Len() int {
return len(p)
}
// 小于(<)就是小顶堆, 大于(>)就是大顶堆
func (p PriorityQueue) Less(i, j int) bool {
return p[i].Val < p[j].Val
}
func (p PriorityQueue) Swap(i, j int) {
p[i], p[j] = p[j], p[i]
return
}
func (p *PriorityQueue) Push(x interface{}) {
*p = append(*p, x.(*ListNode))
}
func (p *PriorityQueue) Pop() interface{} {
old := *p
n := len(old)
x := old[n-1]
*p = old[0 : n-1]
return x
}
func main() {
p := &PriorityQueue{}
heap.Init(p)
node1 := &ListNode{Val: 4}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 2}
node4 := &ListNode{Val: 6}
node5 := &ListNode{Val: 1}
heap.Push(p, node1)
heap.Push(p, node2)
heap.Push(p, node3)
heap.Push(p, node4)
heap.Push(p, node5)
for p.Len() > 0 {
node := heap.Pop(p)
fmt.Print(node.(*ListNode).Val, " ")
}
}
输出:
1 2 3 4 6
最近在leetcode刷题, 遇到一个合并K个升序链表的问题, 就是把K个有序链表合并成一个有序链表
有了上面定义好的优先级队列, 我们可以开始解决问题了
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists)==0{
return nil
}
dummy := &ListNode{Val: -1}
p1 := dummy
// 使用一个优先级队列(小根堆), 每次把堆顶元素(最小值)弹出来
p := &PriorityQueue{}
heap.Init(p)
for i := 0; i < len(lists); i++ {
if lists[i]!=nil{
heap.Push(p, lists[i])
}
}
for p.Len() > 0 {
v := heap.Pop(p).(*ListNode)
p1.Next = v
if v.Next!=nil{
heap.Push(p, v.Next)
}
p1 = p1.Next
}
return dummy.Next
}
// 测试
func main() {
node1 := &ListNode{Val: 3}
node2 := &ListNode{Val: 4}
node1.Next = node2
node3 := &ListNode{Val: 1}
node4 := &ListNode{Val: 2}
node3.Next = node4
node5 := &ListNode{Val: 6}
node4.Next = node5
v := mergeKLists([]*ListNode{node1, node3})
fmt.Println(v)
}
我目前使用的是go1.16.5版本, 这个版本的go还不支持泛型, 所以官方被迫使用interface{}作为容器的参数来保持其兼容性和拓展性, 这就导致目前go的container只能处于一个半成品的状态, go在1.18开始提供了泛型, 易用性将会得到很大的改善.
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。