下麵是golang實現的簡單優先隊列，參考信息可以查看https://golang.org/pkg/container/heap/或者https://golang.google.cn/pkg/container/heap/，後面這個網址也是官方提供的網址，關於這個網頁的說明，可以參考https:// ...
下麵是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函數獲得的值進行類型強轉，使用起來更像是面向對象程式設計的那種方式了。對於需要動態修改優先隊列中成員值的情況，可以參考實現。
