我要评论下面是golang实现的简单优先队列，参考信息可以查看https://golang.org/pkg/container/heap/或者https://golang.google.cn/pkg/container/heap/，后面这个网址也是官方提供的网址，关于这个网页的说明，可以参考https://blog.golang.org/hello-china。
package queue
import "container/heap"
// qitem 表示存储到这个队列中需要实现的接口
type qitem interface {
less(item qitem) bool
}
// priorityqueueimpl 用于优先队列底层实现
type priorityqueueimpl []qitem
// len 获取队列长度
func (pqi priorityqueueimpl) len() int {
return len(pqi)
}
// less 用来进行元素比较
func (pqi priorityqueueimpl) less(i, j int) bool {
return pqi[i].less(pqi[j])
}
// swap 进行交换
func (pqi priorityqueueimpl) swap(i, j int) {
pqi[i], pqi[j] = pqi[j], pqi[i]
}
// push 用来将一个对象压入队列中
func (pqi *priorityqueueimpl) push(x interface{}) {
item := x.(qitem)
*pqi = append(*pqi, item)
}
// pop 将一个对象弹出队列
func (pqi *priorityqueueimpl) pop() interface{} {
old := *pqi
n := len(old)
item := old[n-1]
*pqi = old[0 : n-1]
return item
}
// priorityqueue 实现优先队列
type priorityqueue struct {
priorityqueueimpl
}
// newpriorityqueue 用来构建priorityqueue
func newpriorityqueue() *priorityqueue {
var pq priorityqueue
heap.init(&pq.priorityqueueimpl)
return &pq
}
// push 用来将一个对象压入到队列中
func (pq *priorityqueue) push(item qitem) {
heap.push(&pq.priorityqueueimpl, item)
}
// pop 用来从队列中弹出一个对象
func (pq *priorityqueue) pop() qitem {
return heap.pop(&pq.priorityqueueimpl).(qitem)
}
// front 用来获取当前队列中的最小值
func (pq *priorityqueue) front() qitem {
// 队列中第一位应该就是最小值
return pq.priorityqueueimpl[0]
}
// length 用来获取当前队列的长度
func (pq *priorityqueue) length() int {
return pq.priorityqueueimpl.len()
}
如果希望一个结构可以存储到priorityqueue中，需要实现qitem接口中的函数，即less函数。下面给出一个简单的示例：
type int int
func (i int) less(j qitem) bool {
return i < j.(int)
}
注意func (i int) less(j qitem) bool中的传参是qitem，而不是int，golang当前还不支持泛型，所以，如果想要实现c++的stl的那种效果，应该是不可能的，就算使用反射来使得更多的类型得到支持，也势必会带来很大的性能开销，这个是我不太乐见的。关于将int类型作为参数进行使用，可以参考下面的测试代码，这个测试代码不太规范，不过测试效果应该可以实现：
func test_newpriorityqueue(t *testing.t) {
pq := newpriorityqueue()
pq.push(int(5))
pq.push(int(8))
pq.push(int(3))
first := pq.front()
if first != int(3) {
t.error("first should be 3")
return
}
first = pq.pop()
if first != int(3) {
t.error("first should be 3")
return
}
second := pq.pop()
if second != int(5) {
t.error("second should be 5")
return
}
pq.push(int(1))
length := pq.length()
if length != 2 {
t.error("length should be 2")
return
}
third := pq.front()
if third != int(1) {
t.error("third should be 1")
return
}
third = pq.pop()
if third != int(1) {
t.error("third should be 1")
return
}
fourth := pq.pop()
if fourth != int(8) {
t.error("fourth should be 8")
return
}
length = pq.length()
if length != 0 {
t.error("empty length should be 0")
return
}
}
在实际使用中，可能需要对func (pq *priorityqueue) pop() qitem函数和func (pq *priorityqueue) front() qitem函数获得的值进行类型强转，使用起来更像是面向对象程序设计的那种方式了。对于需要动态修改优先队列中成员值的情况，可以参考实现。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论