# An implementation to priority queue based on linked heap（by golang)

# 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: 

```go
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:
1. When we add a node into heap, we should find the parent node of current node.
2. 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.
![figure](https://img-blog.csdnimg.cn/83b67fdf8ea847eabecb9a99e349bde9.png)


## 代码

The full codes as follows. We implement it by taking priority queue for eample. 


```go
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.

![test result](https://img-blog.csdnimg.cn/36bf0b094b6340d884d3a90a6973ed4c.png)


```go
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)
}


```