一种基于堆的链式优先队列实现（使用golang）
前言
传统的堆使用的是数组实现方式。众所周知数组是定长的，因此给堆的实际使用带来了限制与不便。本文使用基于链式的实现方式。
原理
堆逻辑上是一棵完全二叉树。关于堆的知识不再赘述，可叁考其它博主的博文。
既然是树，使用 链式的实现方式不仅更加直观，而且支持任意长度的节点个树。
本文的树结点定义如下：
type _QueueNode[T interface{}] struct {
parent *_QueueNode[T] // 父结点
left *_QueueNode[T] // 左孩子
right *_QueueNode[T] // 右孩子
last *_QueueNode[T] // 链表上一个结点
next *_QueueNode[T] // 链表下一个结点
data T // 结点数据
}
结合上述定义和下图，可以看出，结点兼顾了两重身份：
- 树结点 （如图中蓝线）
- 链表结点（如图中红线）
之所以引入链表，是因为存粹的树结点不能找到与它同一层的其它结点，而堆的基本操作需要用到它些结点。例如：
- 在堆中加入一个结点时，需要为这个节点寻找一个父结点
- 在堆中删除堆首数据时，会与堆尾元素交换并把堆尾的结点删除，这时就需要能够改变
tail结点为它的上一个结点
代码
完整代码如下。本代码以优先队列为例进行实现：
package structure
/**
优先队列数据结构
最小堆要求，对于任意一个父结点来说，其子结点的值都大于这个父节点
这里实现链式堆
@author cloudea
@date 2022/9/10
*/
type _QueueNode[T interface{}] struct {
parent *_QueueNode[T] // 父结点
left *_QueueNode[T] // 左孩子
right *_QueueNode[T] // 右孩子
last *_QueueNode[T] // 链表上一个结点
next *_QueueNode[T] // 链表下一个结点
data T // 结点数据
}
type PriorityQueue[T interface{}] struct {
head *_QueueNode[T] // 头节点
tail *_QueueNode[T] // 尾结点
length int // 堆的长度
lessThan func(data1 T, data2 T) bool // 比较函数
}
func NewPriorityQueue[T interface{}](lessThan func(data1 T, data2 T) bool) *PriorityQueue[T] {
if lessThan == nil {
panic("lessThan fun can not be nil!")
}
node := &_QueueNode[T]{}
return &PriorityQueue[T]{
head: node,
tail: node,
length: 0,
lessThan: lessThan,
}
}
func (this *PriorityQueue[T]) Empty() bool {
return this.Size() == 0
}
func (this *PriorityQueue[T]) Size() int {
return this.length
}
func (this *PriorityQueue[T]) Front() T {
if this.Empty() {
panic("heap is empty!")
}
return this.head.next.data
}
func (this *PriorityQueue[T]) Back() T {
if this.Empty() {
panic("heap is empty!")
}
return this.tail.data
}
func (this *PriorityQueue[T]) Enqueue(data T) {
if this.Empty() {
node := &_QueueNode[T]{
parent: nil,
data: data,
}
this.head.next = node
this.tail = node
} else {
// 把节点加入树中
var parent *_QueueNode[T] = nil
if this.tail.parent == nil {
parent = this.tail
} else {
if this.tail.parent.right == nil {
parent = this.tail.parent
} else {
parent = this.tail.parent.next
}
}
node := &_QueueNode[T]{
parent: parent,
left: nil,
right: nil,
last: this.tail,
next: nil,
data: data,
}
if parent.left == nil {
parent.left = node
} else {
parent.right = node
}
this.tail.next = node
this.tail = this.tail.next
// 循环上浮
for parent != nil && this.lessThan(node.data, parent.data) {
node.data, parent.data = parent.data, node.data
node = parent
parent = parent.parent
}
}
this.length++
}
func (this *PriorityQueue[T]) Dequeue() T {
if this.Empty() {
panic("heap is empty!")
}
if this.Size() == 1 {
popedNode := this.head.next
this.head.next = nil
this.tail = this.head
this.length = 0
return popedNode.data
}
// 把最后一个结点与第一个结点的值交换
this.head.next.data, this.tail.data = this.tail.data, this.head.next.data
// 删除最后一个结点
if this.tail.parent.left == this.tail {
this.tail.parent.left = nil
} else {
this.tail.parent.right = nil
}
popedNode := this.tail
this.tail.last.next = nil
this.tail = this.tail.last
// 循环下沉
parent := this.head.next
for parent.left != nil || parent.right != nil {
var minChild *_QueueNode[T] = nil
if parent.right == nil || this.lessThan(parent.left.data, parent.right.data) {
minChild = parent.left
} else {
minChild = parent.right
}
if this.lessThan(minChild.data, parent.data) {
minChild.data, parent.data = parent.data, minChild.data
parent = minChild
continue
}
break
}
this.length--
return popedNode.data
}
测试
下面代码及运行结果测试了该实现的正确性：
func TestPriorityValue(t *testing.T) {
fmt.Println("测试")
list1 := structure.NewList[int]()
list2 := structure.NewList[int]()
cmp := func(data1 int, data2 int) bool { return data1 < data2 }
queue := structure.NewPriorityQueue[int](cmp)
// 随机生成100个数
rand.Seed(time.Now().UnixMicro() % 36)
for i := 0; i < 100; i++ {
number := rand.Intn(100)
list1.Enqueue(number)
queue.Enqueue(number)
}
// 把堆的数据取出放到list2
for i := 0; i < 100; i++ {
list2.Enqueue(queue.Dequeue())
}
// 把list1排序后与list2比较，看是否一致
list1.Sort(cmp)
if fmt.Sprint(list1) != fmt.Sprint(list2) {
panic("not equal")
}
fmt.Println(list2)
}