golang实现一个优先队列

近期要用golang 实现一个优先队列，优先队列的实现最早是在 c语言书籍：

参考书籍：

<<数据结构和算法c>> 

小根堆实现：

package main

import "fmt"

type StreamPriorityQueueData struct {
	key   int
	value int
}

type StreamPriorityQueue struct {
	caches   []StreamPriorityQueueData
	size     int
	capacity int
}

func NewStreamPriorityQueue(size int) *StreamPriorityQueue {
	return &StreamPriorityQueue{
		caches:   make([]StreamPriorityQueueData, size),
		capacity: size,
	}
}

func (q *StreamPriorityQueue) GetQueueTop() StreamPriorityQueueData {
	if len(q.caches) == 0 {
		return StreamPriorityQueueData{}
	}

	return q.caches[0]
}

func (q *StreamPriorityQueue) EnQueue(data StreamPriorityQueueData) {
	if q.size == q.capacity {
		return
	}

	q.size++

	var i int
	for i = q.size; q.caches[i/2].key > data.key; i /= 2 {
		q.caches[i] = q.caches[i/2]
	}
	q.caches[i] = data
}

func (q *StreamPriorityQueue) DeQueue() StreamPriorityQueueData {
	if q.size == 0 {
		return q.caches[0]
	}

	minElements := q.caches[1]
	lastElements := q.caches[(q.size)]

	var i int
	var child int

	for i = 1; i*2 <= q.size; i = child {
		child = i * 2

		//左右子节点比较,选较小的一方
		if child != q.size && (q.caches[child+1].key < q.caches[child].key) {
			child++
		}

		//最后一个元素和子节点比较，如果最后一个元素大，上提子节点
		if lastElements.key > q.caches[child].key {
			q.caches[i] = q.caches[child]
		} else {
			break
		}
	}
	q.caches[i] = lastElements
	fmt.Println(minElements)
	return minElements
}

func main() {
	q := NewStreamPriorityQueue(8)
	d := StreamPriorityQueueData{
		key:   1,
		value: 1,
	}
	q.EnQueue(d)

	d1 := StreamPriorityQueueData{
		key:   2,
		value: 2,
	}
	q.EnQueue(d1)

	d2 := StreamPriorityQueueData{
		key:   3,
		value: 3,
	}
	q.EnQueue(d2)

	d3 := StreamPriorityQueueData{
		key:   4,
		value: 4,
	}
	q.EnQueue(d3)

	d4 := StreamPriorityQueueData{
		key:   5,
		value: 5,
	}
	q.EnQueue(d4)

	q.DeQueue()
	q.DeQueue()
	q.DeQueue()
	q.DeQueue()
	q.DeQueue()

	q.EnQueue(d3)
	q.DeQueue()

}

大根堆实现：

package main

import "fmt"

type StreamPriorityQueueData struct {
	key   int
	value int
}

type StreamPriorityQueue struct {
	caches   []StreamPriorityQueueData
	size     int
	capacity int
}

func NewStreamPriorityQueue(size int) *StreamPriorityQueue {
	return &StreamPriorityQueue{
		caches:   make([]StreamPriorityQueueData, size),
		capacity: size,
	}
}

func (q *StreamPriorityQueue) GetQueueTop() StreamPriorityQueueData {
	if len(q.caches) == 0 {
		return StreamPriorityQueueData{}
	}

	return q.caches[0]
}

func (q *StreamPriorityQueue) swap(x *StreamPriorityQueueData, y *StreamPriorityQueueData) {
	tmp := *x
	*x = *y
	*y = tmp
}

func (q *StreamPriorityQueue) adjustUp() {
	child := q.size
	parent := (child - 1) / 2
	for q.caches[parent].key < q.caches[child].key {
		q.swap(&(q.caches[parent]), &(q.caches[child])) //进行交换
		child = parent
		parent = (child - 1) / 2
	}
}

func (q *StreamPriorityQueue) adjustDown(n int, parent int) {
	child := parent*2 + 1
	for child < n {
		//比较左孩子还是右孩子大
		if child+1 < n && q.caches[child+1].key > q.caches[child].key {
			child++
		}
		if q.caches[child].key > q.caches[parent].key {
			q.swap(&q.caches[child], &q.caches[parent])
			parent = child
			child = parent*2 + 1
		} else {
			break
		}
	}
}

func (q *StreamPriorityQueue) EnQueue(data StreamPriorityQueueData) {
	if q.size == q.capacity {
		return
	}
	q.caches[q.size] = data
	q.adjustUp()
	q.size++
}

func (q *StreamPriorityQueue) DeQueue() StreamPriorityQueueData {
	if q.size == 0 {
		return q.caches[0]
	}

	q.swap(&q.caches[0], &q.caches[q.size-1])
	q.size--
	q.adjustDown(q.size, 0)
	return q.caches[q.size]
}

func main() {
	q := NewStreamPriorityQueue(8)
	d := StreamPriorityQueueData{
		key:   1,
		value: 1,
	}
	q.EnQueue(d)

	d1 := StreamPriorityQueueData{
		key:   2,
		value: 2,
	}
	q.EnQueue(d1)

	d2 := StreamPriorityQueueData{
		key:   3,
		value: 3,
	}
	q.EnQueue(d2)

	d3 := StreamPriorityQueueData{
		key:   4,
		value: 4,
	}
	q.EnQueue(d3)

	d4 := StreamPriorityQueueData{
		key:   5,
		value: 5,
	}
	q.EnQueue(d4)

	fmt.Println(q.DeQueue().key)
	fmt.Println(q.DeQueue().key)
	fmt.Println(q.DeQueue().key)
	fmt.Println(q.DeQueue().key)
	fmt.Println(q.DeQueue().key)
	fmt.Println(q.DeQueue().key)

}