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:

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.

代码

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