2. Golang优先队列（基于堆排序实现）

优先队列

堆排序

排完序以后，就可以从队列里面取出想要的值。

// 最大堆、最小堆

// 接口实现比大小
type Item interface {
	Less(than Item) bool
}

type Int int

func (x Int) Less(than Item) bool {
	return x < than.(Int)
}

// 最小堆
type Heap struct {

	// 数据
	data []Item

	// 是否最小值
	min bool

	// 锁
	lock *sync.Mutex
}

// 初始化堆
func NewHeap() *Heap {
	return &Heap{
		data: make([]Item, 0),
		min:  true,
		lock: new(sync.Mutex),
	}
}

// 初始化最小堆
func NewMin() *Heap {
	return &Heap{
		data: make([]Item, 0),
		min:  true,
		lock: new(sync.Mutex),
	}
}

// 初始化最大堆
func NewMax() *Heap {
	return &Heap{
		data: make([]Item, 0),
		min:  false,
		lock: new(sync.Mutex),
	}
}

// 判断是否为空
func (h *Heap) isEmpty() bool {
	return len(h.data) == 0
}

// 堆长度
func (h *Heap) Len() int {
	return len(h.data)
}

// 获取数据
func (h *Heap) Get(index int) Item {
	return h.data[index]
}

// 插入数据
func (h *Heap) Insert(it Item) {

	h.lock.Lock()
	defer h.lock.Unlock()

	// 插入数据
	h.data = append(h.data, it)

	h.siftUp()
}

// 比较大小
func (h *Heap) Less(a, b Item) bool {

	if h.min {
		return a.Less(b)
	} else {
		return b.Less(a)
	}
}

// 压缩，弹出一个
func (h *Heap) Extract() (el Item) {

	h.lock.Lock()
	defer h.lock.Unlock()

	if h.Len() == 0 {
		return
	}

	// 第一个
	el = h.data[0]

	// 最后一个
	last := h.data[h.Len()-1]

	// 如果只有一个数据
	if h.Len() == 1 {
		h.data = nil
		return
	}

	// 排除了第一个
	h.data = append([]Item{last}, h.data[1:h.Len()-1]...)
	h.siftDown()
	return
}

// 弹出一个极大值
func (h *Heap) siftUp() {

	// 堆排序循环  n 2n+1
	for i, parent := h.Len()-1, h.Len()-1; i > 0; i = parent {

		// 顶点
		parent = i / 2

		// 对比子节点和顶点
		if h.Less(h.Get(i), h.Get(parent)) {
			h.data[parent], h.data[i] = h.data[i], h.data[parent]
		} else {
			break
		}
	}
}

// 弹出一个极小值
func (h *Heap) siftDown() {

	// 堆排序循环  n 2n+1
	for i, child := 0, 1; i < h.Len() && i*2+1 < h.Len(); i = child {

		// 子结点
		child = i*2 + 1

		// 循环左右子结点
		if child+1 <= h.Len()-1 && h.Less(h.Get(child+1), h.Get(child)) {
			child++
		}

		// 对比顶点和子结点
		if h.Less(h.Get(i), h.Get(child)) {
			break
		}

		// 交换顶点和子结点的值
		h.data[i], h.data[child] = h.data[child], h.data[i]
	}
}


// 优先队列（基于堆）
type PriorityQueue struct {

	// 数据
	data *Heap.Heap
}

// 初始化优先队列（最大堆模式）
func NewMaxPriorityQueue() *PriorityQueue {
	return &PriorityQueue{data: Heap.NewMax()}
}

// 初始化优先队列（最小堆模式）
func NewMinPriorityQueue() *PriorityQueue {
	return &PriorityQueue{data: Heap.NewMin()}
}

// 优先队列项
type PriorityItem struct {

	// 数据
	value interface{}

	// 优先级
	level int
}

// 初始化优先队列项
func NewPriorityItem(value interface{}, level int) *PriorityItem {
	return &PriorityItem{
		value: value,
		level: level,
	}
}

// 比较优先级
func (x PriorityItem) Less(than Heap.Item) bool {
	return x.level < than.(PriorityItem).level
}

// 队列的长度
func (pq *PriorityQueue) Len() int {
	return pq.data.Len()
}

// 插入
func (pq *PriorityQueue) Insert(el PriorityItem) {
	pq.data.Insert(el)
}

// 压缩
func (pq *PriorityQueue) Extract() PriorityItem {
	return pq.data.Extract().(PriorityItem)
}

// 修改优先级
func (pq *PriorityQueue) ChangeLevel(val interface{}, level int) {

	// 新队列
	storage := NewQueue()

	// 旧队列最小的值
	popped := pq.Extract()

	// 不等于传入值
	for val != popped.value {

		// 旧队列为空
		if pq.Len() == 0 {
			return
		}

		// 压入数据
		storage.Push(popped)

		// 数据处理
		popped = pq.Extract()
	}

	// 找到该值
	popped.level = level

	// 插入数据
	pq.data.Insert(popped)

	// 其余数据重新放入优先队列
	for storage.Len() > 0 {
		pq.data.Insert(storage.Shift().(Heap.Item))
	}