golang实现的简单优先队列

下面是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函数获得的值进行类型强转，使用起来更像是面向对象程序设计的那种方式了。对于需要动态修改优先队列中成员值的情况，可以参考实现。