golang实现优先队列,以前写的一个简单例子,现上传备份
package testimport ("container/heap""fmt"
)func Test() {// 测试一下任务队列// 1、首先测试是标准任务队列,队列之中的元素是结构体Personpq := &AgePQ{}heap.Init(pq)ages := []int{2, 3, 1, 6, 5}for i := range ages {tem := &Person{Age: ages[i]}heap.Push(pq, tem)}// 查看pq情况fmt.Println(heap.Pop(pq).(*Person).Age) //6fmt.Println(heap.Pop(pq).(*Person).Age) //5fmt.Println(heap.Pop(pq).(*Person).Age) //3fmt.Println(heap.Pop(pq).(*Person).Age) //2fmt.Println(heap.Pop(pq).(*Person).Age) //1// 这里要注意一下pop方法是在队列的顶进行的操作,如果是升序,则pop出的是最小的值,降序则pop出的是最大的值fmt.Println("—————我是传说中的分割线————")// 2、接下来测试的是int元素所组成的优先队列pq1 := &PQ_of_int{}heap.Init(pq1)for i := range ages {heap.Push(pq1, ages[i])}fmt.Println(heap.Pop(pq1).(int)) //1fmt.Println(heap.Pop(pq1).(int)) //2fmt.Println(heap.Pop(pq1).(int)) //3fmt.Println(heap.Pop(pq1).(int)) //5fmt.Println(heap.Pop(pq1).(int)) //6// 测试结果显示,这两个类型的优先队列都是能完成的
}// 结构体优先队列
type Person struct {Age int
}
type AgePQ []*Personfunc (pq AgePQ) Len() int {return len(pq)
}
func (pq AgePQ) Less(i, j int) bool {// 我们这按照一个降序return pq[i].Age > pq[j].Age
}
func (pq AgePQ) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]
}// 两个队列独有的方法
func (pq *AgePQ) Push(x any) {item := x.(*Person)*pq = append(*pq, item)
}
func (pq *AgePQ) Pop() any {if pq.Len() == 0 {return nil}last := (*pq)[pq.Len()-1]*pq = (*pq)[:(pq.Len() - 1)]return last
}// 简单的int组成的优先队列
type PQ_of_int []intfunc (pq PQ_of_int) Len() int {return len(pq)
}
func (pq PQ_of_int) Less(i, j int) bool {// 这里是一个升序return pq[i] < pq[j]
}
func (pq PQ_of_int) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PQ_of_int) Push(x any) {*pq = append(*pq, x.(int))
}
func (pq *PQ_of_int) Pop() any {if pq.Len() == 0 {return nil}last := (*pq)[pq.Len()-1]*pq = (*pq)[:pq.Len()-1]return last
}
主要测试了两个优先队列,一个队列是针对Person结构体,第二个队列单纯就是int切片
需要注意以下几个点:
1、pop和push行为最好不要直接调用,而是借助heap.Pop()这样的方法
2、pop行为可能在js当中表示删除数组的最后一个值,这里pop行为是可以自定义的,我将pop行为定义成删除队列最后的值,而真实运行起来,却是删除队列的Top值,比如这里的PQ_of_int,我在Less方法之中定义的是一个升序,但是最后pop出来的确实12356这样的顺序,可能这里有些说法我不是很清楚