1 篇文章 含有標籤「priority-queue」

前陣子，我耗費不少心力在撰寫 jr-dragon/olivine，這是一個為教學目的設計的純 Go 語言實現的 Redis 相容服務。

在研究的過程中，我不禁開始思考關於 Priority Queue 這個資料結構，在大學課程的訓練中，我們往往被教導著：Priority Queue 就是 Binary Heap 的一種應用，然而實際上這這種說並不完全正確。

Priority Queue 作為一種抽象資料結構，其實並沒有規定底層必須怎麼實現：只要能夠符合特性定義，單純的陣列都可以稱其為 Pirority Queue：

type pq []int

func (q pq) Push(n int) {
	q = append(q, n)
}

func (q pq) Pop() (int, bool) {
	if len(q) == 0 {
		return 0, false
	}

	max := q[0]
	for _, n := range q {
		if max < n {
			max = n
		}
	}

	return max, true
}

以上是一個由陣列（Go Slice）所構成、符合定義的 Priority Queue，但顯而易見地其複雜度不盡如人意。