Storage address of GitHub warehouse: https://github.com/hlccd/goSTL
summary
This time, the heap is implemented in the form of Complete Binary Tree.
heap is a general term for a special class of data structures. heap is usually an array object that can be regarded as a tree. heap always satisfies the following properties:
- The value of a node in the heap is always not greater than or less than the value of its parent node;
- Heap is always a complete binary tree.
The main characteristics of heap are: its parent node must be less than or equal to the left and right child nodes (the small top heap is used in this article, and the size of large top heap is the opposite).
In this practice, the complete binary tree is used.
principle
Complete binary tree implementation heap
For a complete binary tree, first of all, except that the bottom layer of the complete binary tree may be dissatisfied, the other upper layers must be full. For a node of a complete binary tree, its left and right nodes do not use subscripts to obtain, but use its pointers to find.
At the same time, in the implementation, you need to use size to record how many elements are accumulated in the heap.
In the process of insertion and deletion, similar to the array implementation, the insertion needs to be inserted at the last node, and then rise. In the process of deletion, the first node needs to be replaced by the tail node, and then fall to the first point. In these two processes, the core point is how to find the tail node.
Find tail node
When finding the tail node, you can refer to the subscript in the array implementation process. At the same time, because you only need to find the tail node, and the subscript of the tail node happens to be the value of size-1.
Therefore, we can use the number of elements currently stored in the heap to find the last node and its parent node.
Similar to the array, the "subscript" starts from 0. Observe the nodes inserted in the previous group: (size+1) and are binary
-
First node - > 10
-
Second node - > 11
-
Third node - > 100
-
Fourth node - > 101
-
Fifth node - > 110
-
Sixth node - > 111
-
Seventh node - > 1000
-
Eighth node - > 1001
-
Ninth node - > 1010
-
······
At the same time, by observing its position in the binary tree, it can find the parent node of the inserted node according to its subscript converted to binary value and 1010101 string, for example:
- The 11th node: 1100. The path obtained by this node from the root node is: right, left and left
- The 15th node: 10000. The path obtained by this node from the root node is: left
- The 18th node: 10011 the path obtained by the node from the root node is: left, right and right
- ···
It can be seen from the observation that for the added node, the current size+1 can be converted into binary through its subscript, and then the first bit can be deleted. According to the subsequent bit bits, 1 can be regarded as the right node, and 0 can be transferred to the left node to find the corresponding node. If you want to find its parent node, you only need to reduce one jump.
For deleting a node, you do not need to reduce the size first. You can directly find the end node. The method is the same as above.
Add policy
After solving the problem of finding the tail node and its parent node, the addition strategy is basically the same as the implementation in the form of array.
That is, when inserting a node, you can first put it at the end of the complete binary search, and then compare it with its parent node according to the inserted value. If the inserted value is less than the parent node, exchange the two node values, then compare the exchanged node with its parent node, and repeat the process until it reaches the vertex or does not meet the conditions.
Add step
- The corresponding tail node and its parent node are found by the algorithm of finding the tail node, and the parent node is used to insert
- After the node is placed in the tail, it is exchanged by comparing the values of the node and the parent node
- If the exchange conditions are met, repeat the process back to 2
- When the top is reached or the exchange conditions are not met, the addition is completed and the insertion is completed
Delete policy
The deletion strategy of the heap implemented by the complete binary tree is similar to the heap deletion strategy implemented in the form of array. The difference is that a special method to find the tail node and its parent node is required (introduced above).
That is, different from the case of directly using the tail node when adding, because the first node is deleted, and deleting at the same time needs to reduce a space, you can consider exchanging the first node or directly overwriting the first node with the tail node, so as to delete the first node and use the parent node of the tail node found before, Set the pointer on the corresponding side to nil to delete the tail node.
After the previous process is completed, the first node and are deleted, but the new first node moved to the first node may not meet the situation that the parent node of the priority queue must be less than or equal to the left and right child nodes. Therefore, the next operation should be carried out by comparing the parent node and its left and right child nodes, that is, when there is a node within the array range and greater than the parent node, the two nodes will be exchanged, The process is then recursive until the bottom is reached or the condition is not met.
In the comparison process, first compare the situation of the left node and the parent node, and then compare the situation of the right node to find the smallest side to descend.
Delete step
- Find the parent node of the tail node by finding the tail node, and overwrite the first node with the tail node.
- Delete tail node
- Take the first node as the parent node and judge whether the left and right nodes exist and whether the existing left and right nodes are smaller than the parent node,
- Compare the left and right sides, find the smallest side that is smaller than the parent node and drop it. At the same time, return to the 3 process for recursive descent
- When the bottom is touched or the conditions are not met, the descent ends and the deletion is completed.
realization
cbTree is a complete binary tree structure. This instance stores the root node of the binary tree and how many elements have been stored in the binary tree. The comparator used for sorting in the binary tree is passed in during creation. If not, it is found from the default comparator when inserting the first node.
type cbTree struct {
root *node //Root node pointer
size uint64 //Number of storage elements
cmp comparator.Comparator //comparator
mutex sync.Mutex //Concurrency control lock
}
Node tree node structure. This node is a tree node of a complete binary tree. In addition to saving the bearing elements, this node will also save the pointers of the parent node and the left and right child nodes.
type node struct {
value interface{} //Elements stored in nodes
parent *node //Parent node pointer
left *node //Left node pointer
right *node //Right node pointer
}
Interface
type cbTreer interface {
Iterator() (i *Iterator.Iterator) //Returns all elements that contain the binary tree
Size() (num uint64) //Returns the number of elements saved in the binary tree
Clear() //Empty the binary tree
Empty() (b bool) //Judge whether the binary tree is empty
Push(e interface{}) //Insert element e into binary tree
Pop() //Pop top element from binary tree
Top() (e interface{}) //Returns the top element of the binary tree
}
New
Create a cbTree full binary tree container and return it. The initial root node is nil. If there is an incoming comparator, set the first comparator as the comparator of the binary tree.
func New(Cmp ...comparator.Comparator) (cb *cbTree) {
//Judge whether there is an incoming comparator. If so, set it as the default comparator of the binary tree
var cmp comparator.Comparator
if len(Cmp) > 0 {
cmp = Cmp[0]
}
return &cbTree{
root: nil,
size: 0,
cmp: cmp,
mutex: sync.Mutex{},
}
}
newNode
Create a complete binary tree node and return it. Take the incoming element e as the bearing element of the node, the incoming parent node as its parent node, and the left and right nodes as nil.
func newNode(parent *node, e interface{}) (n *node) {
return &node{
value: e,
parent: parent,
left: nil,
right: nil,
}
}
Iterator
Take the complete binary tree of cbTree as the receiver, and put all the saved elements in the binary tree into the iterator in the form of prefix sequence from the root node.
func (cb *cbTree) Iterator() (i *Iterator.Iterator) {
if cb == nil {
cb = New()
}
cb.mutex.Lock()
es := cb.root.frontOrder()
i = Iterator.New(&es)
cb.mutex.Unlock()
return i
}
frontOrder
Take the node node as the receiver and return the node set with the prefix sequence.
func (n *node) frontOrder() (es []interface{}) {
if n == nil {
return es
}
es = append(es, n.value)
if n.left != nil {
es = append(es, n.left.frontOrder()...)
}
if n.right != nil {
es = append(es, n.right.frontOrder()...)
}
return es
}
Size
Take the complete binary tree of cbTree as the receiver and return the number of elements currently contained in the container. If the container is nil, return 0.
func (cb *cbTree) Size() (num uint64) {
if cb == nil {
cb = New()
}
return cb.size
}
Clear
Take the complete binary tree of cbTree as the receiver, empty the elements carried in the container, and set the size of the container to 0.
func (cb *cbTree) Clear() {
if cb == nil {
cb = New()
}
cb.mutex.Lock()
cb.root = nil
cb.size = 0
cb.mutex.Unlock()
}
Empty
Take the cbTree complete binary tree as the receiver to judge whether the complete binary tree contains elements. If it contains elements, it is not empty and returns false. If it does not contain elements, it is empty and returns true. If the container does not exist, it returns true.
func (cb *cbTree) Empty() (b bool) {
if cb == nil {
cb = New()
}
return cb.size == 0
}
lastParent
The node node is used as the receiver, and the last parent node is simulated to be found by converting it into binary according to the incoming value. Because the path to find the parent node is equivalent to the intermediate value except the first one after converting it into binary, the scheme is feasible.
func (n *node) lastParent(num uint64) (ans *node) {
if num > 3 {
//Remove the binary value at the end
arr := make([]byte, 0, 64)
ans = n
for num > 0 {
//Convert to binary
arr = append(arr, byte(num%2))
num /= 2
}
//Remove the first binary value
for i := len(arr) - 2; i >= 1; i-- {
if arr[i] == 1 {
ans = ans.right
} else {
ans = ans.left
}
}
return ans
}
return n
}
Push
Take the complete binary tree of cbTree as the receiver, insert the element e into the binary tree, put it into the last position of the complete binary tree, and then raise the element. If the binary tree itself is empty, set the root node as the inserted node element directly.
func (cb *cbTree) Push(e interface{}) {
if cb == nil {
cb=New()
}
cb.mutex.Lock()
if cb.Empty() {
if cb.cmp == nil {
cb.cmp = comparator.GetCmp(e)
}
if cb.cmp == nil {
cb.mutex.Unlock()
return
}
cb.root = newNode(nil, e)
cb.size++
} else {
cb.size++
cb.root.insert(cb.size, e, cb.cmp)
}
cb.mutex.Unlock()
}
insert
Take the node node as the receiver, insert the element e from the node, find the last parent node according to the incoming num for inserting the last bit value, and then increase the inserted value.
func (n *node) insert(num uint64, e interface{}, cmp comparator.Comparator) {
if n == nil {
return
}
//Find the last parent node
n = n.lastParent(num)
//Insert element into last node
if num%2 == 0 {
n.left = newNode(n, e)
n = n.left
} else {
n.right = newNode(n, e)
n = n.right
}
//Raise the inserted node
n.up(cmp)
}
up
Take the node node as the receiver to rise the node. When the node exists and the parent node exists, if the node is smaller than the husband node, it can continue to rise after exchanging the two node values.
func (n *node) up(cmp comparator.Comparator) {
if n == nil {
return
}
if n.parent == nil {
return
}
//Both the node and the parent node exist
if cmp(n.parent.value, n.value) > 0 {
//The node value is less than the parent node value. Exchange the two node values and continue to rise
n.parent.value, n.value = n.value, n.parent.value
n.parent.up(cmp)
}
}
Pop
Take the cbTree complete binary tree as the receiver, delete the top element e from the complete binary tree, exchange the top element with the last element, then delete the last element, and then sink the top element.
func (cb *cbTree) Pop() {
if cb == nil {
return
}
if cb.Empty() {
return
}
cb.mutex.Lock()
if cb.size == 1 {
//The binary tree has only the root node, which can be deleted directly
cb.root = nil
} else {
//After the root node of the binary tree is deleted, other nodes can be generated as follow nodes
cb.root.delete(cb.size, cb.cmp)
}
cb.size--
cb.mutex.Unlock()
}
delete
Take the node node as the receiver, delete the node from the, find the last parent node for replacement and deletion according to the incoming num, and then sink the replaced value
func (n *node) delete(num uint64, cmp comparator.Comparator) {
if n == nil {
return
}
//Find the last parent node
ln := n.lastParent(num)
if num%2 == 0 {
n.value = ln.left.value
ln.left = nil
} else {
n.value = ln.right.value
ln.right = nil
}
//Sink the node after exchange
n.down(cmp)
}
down
Take the node node as the receiver and sink the node. When there is a right node and less than its own element, exchange with the right node and continue to sink. Otherwise, when there is a left node and less than its own element, exchange with the left node and continue to sink. When both left and right nodes do not exist or are greater than its own element, the sinking stops.
func (n *node) down(cmp comparator.Comparator) {
if n == nil {
return
}
if n.right != nil && cmp(n.left.value, n.right.value) >= 0 {
n.right.value, n.value = n.value, n.right.value
n.right.down(cmp)
return
}
if n.left != nil && cmp(n.value, n.left.value) >= 0 {
n.left.value, n.value = n.value, n.left.value
n.left.down(cmp)
return
}
}
Top
Take the cbTree complete binary tree as the receiver, return the top element of the complete binary tree, and return nil when the complete binary tree does not exist or the root node does not exist.
func (cb *cbTree) Top() (e interface{}) {
if cb == nil {
cb=New()
}
cb.mutex.Lock()
e = cb.root.value
cb.mutex.Unlock()
return e
}
Use example
package main
import (
"fmt"
"github.com/hlccd/goSTL/data_structure/heap"
"sync"
)
func main() {
h := heap.New()
wg := sync.WaitGroup{}
for i := 0; i < 10; i++ {
wg.Add(1)
go func(num int) {
h.Push(num)
}(i)
}
fmt.Println("Use the iterator to output all the elements stored in the heap:")
for i := h.Iterator(); i.HasNext(); i.Next() {
fmt.Println(i.Value())
}
fmt.Println("Output the top elements in turn:")
for !h.Empty() {
fmt.Println(h.Top())
h.Pop()
}
}
Note: Although the addition process is random, it is relatively orderly, so no matter how it is added, it is an output result
Use the iterator to output all the elements stored in the heap:
0
3
4
6
8
5
9
1
2
7
Output the top elements in sequence:
0
1
2
3
4
5
6
7
8
9