An implementation to priority queue based on linked heap（by golang)
Published
•4 min read
Y
never give up!
introduction
The traditional ways to implement heap are to use arrays! As we all know, the length of array is fixed. Since that, the usage of heap has many limitaions and usually is inconvinient. This article uses the link-based implementation.
principle
Heap is a complete binary tree logically. We will not cover the basis of heap. Readers can refer to other materials. Now that heap is a tree, the link-based implementaion is not only intutional but also supporting any number of tree nodes.
Tree node defines here:
type _QueueNode[T interface{}] struct {
parent *_QueueNode[T] // pointer to the parent node
left *_QueueNode[T] // pointer to the left child
right *_QueueNode[T] // pointer to the right child
last *_QueueNode[T] // the prior node of the current node
next *_QueueNode[T] // the next node of the current node
data T // data
}
As the above definations and the follow figure, there are tow roles on a node.
- tree node （as shown in blue lines）
- link node（as shown in red lines）
The reason we have a linked list is we can not find the other tree nodes of the pure tree node at the same level. However, the basic operations of heap need it. For examples:
- When we add a node into heap, we should find the parent node of current node.
- When we delete the first data in heap, we will exchange it with the rear node of heap and delete the rear node. In this time, the pointer to the rear node should be changed to the prior one.
代码
The full codes as follows. We implement it by taking priority queue for eample.
package structure
/**
priority queue data structure
We implement small root heap here.
@author cloudea
@date 2022/9/10
*/
type _QueueNode[T interface{}] struct {
parent *_QueueNode[T] // pointer to the parent node
left *_QueueNode[T] // pointer to the left child
right *_QueueNode[T] // pointer to the right child
last *_QueueNode[T] // the prior node of the current node
next *_QueueNode[T] // the next node of the current node
data T // data
}
type PriorityQueue[T interface{}] struct {
head *_QueueNode[T] // head node
tail *_QueueNode[T] // rear node
length int // the length of heap
lessThan func(data1 T, data2 T) bool // comparation function deciding which one is smaller
}
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 {
//add node into the tree
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
// rise circularly
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
}
// swap the value of the rear node with the value in the first node
this.head.next.data, this.tail.data = this.tail.data, this.head.next.data
// delete the rear node
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
// sink circularly
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
}
Test
the following codes tested the correctness of our implementation.
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)
// randomly generating 100 numbers
rand.Seed(time.Now().UnixMicro() % 36)
for i := 0; i < 100; i++ {
number := rand.Intn(100)
list1.Enqueue(number)
queue.Enqueue(number)
}
// take the data of heap into list2
for i := 0; i < 100; i++ {
list2.Enqueue(queue.Dequeue())
}
// compare the consistant of list1 and list2 after sorting
list1.Sort(cmp)
if fmt.Sprint(list1) != fmt.Sprint(list2) {
panic("not equal")
}
fmt.Println(list2)
}
