Analysis of GO language heap

Contents of this section

• heap usage
• Methods provided by heap
• Analysis of heap source code
• Using heap to implement priority queue

1. Use of heap

In the go language standard library container, three data types are implemented: heap,list,ring and list, which have been written in the previous article. Now we want to write the source code analysis of heap.

First, learn how to use heap. Of course, the first step is to import the package. The code is as follows:

package main

import (
	"container/heap"
	"fmt"
)

The data structure used by this heap is the minimum binary tree, that is, the root node is smaller than all values of the left subtree and the right subtree. The source code only implements an interface, which is defined as follows:

type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

It can be seen from this interface that it inherits the sort.Interface interface. What is the definition of sort.Interface? The source code is as follows:

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

In other words, if we want to use the heap provided by the go standard library, we must implement the methods defined by these interfaces. The methods to be implemented are as follows:

• Len() int
• Less(i, j int) bool
• Swap(i, j int)
• Push(x interface{})
• Pop() interface{}

Only when the data types of these five methods are implemented can we use the heap provided by the go standard library. The following simple example is to define an IntHeap type and implement the above five methods.

type IntHeap []int  // Define a type

func (h IntHeap) Len() int { return len(h) }  // Bind len method, return length
func (h IntHeap) Less(i, j int) bool {  // Bind less method
	return h[i] < h[j]  // If h [i] < h [J] generates a small root heap, if h [i] > H [J] generates a large root heap
}
func (h IntHeap) Swap(i, j int) {  // Bind the swap method and exchange the two element positions
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Pop() interface{} {  // Bind the pop method, take out the last element and return it
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *IntHeap) Push(x interface{}) {  // Bind the push method and insert a new element
	*h = append(*h, x.(int))
}

After implementing these five methods for IntHeap, we can use heap. The following are the specific methods:

func main() {
	h := &IntHeap{2, 1, 5, 6, 4, 3, 7, 9, 8, 0}  // Create slice
	heap.Init(h)  // Initialize heap
	fmt.Println(*h)
	fmt.Println(heap.Pop(h))  // Call pop
	heap.Push(h, 6)  // Call push
	fmt.Println(*h)
	for len(*h) > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}

}
Output results:
[0 1 3 6 2 5 7 9 8 4]
0
[1 2 3 6 4 5 7 9 8 6]
1 2 3 4 5 6 6 7 8 9 

The above is the use of heap.

2. Methods provided by heap

heap provides few methods, as follows:

h := &IntHeap{3, 8, 6}  // Create raw data of type IntHeap
func Init(h Interface)  // Initialize heap to generate small root heap (or large root heap)
func Push(h Interface, x interface{})  // Insert content into the heap
func Pop(h Interface) interface{}  // pop content from the top of the heap
func Remove(h Interface, i int) interface{}  // Deletes data from the specified location and returns the deleted data
func Fix(h Interface, i int)  // The priority queue uses this method for heap rebalancing after the data from i location is changed

3. Analysis of heap source code

The internal implementation of heap uses the minimum (maximum) heap, and the index sorting starts from the root node, then the left subtree and the right subtree. The down and up of the internal implementation means that the minimum (maximum) heap is guaranteed downward and the minimum (maximum) heap is guaranteed upward for an element in the heap, respectively.

When an element is inserted into the heap, the element is inserted into the last node of the right subtree, then up is called to ensure the smallest (maximum) stack.

When pushing an element from the heap, first exchange the element with the last node of the right subtree, then pop up the last node, and then call down to root to ensure the minimum (maximum) heap.

OK, start analyzing the source code:

First, before using the heap, you must call its Init method to initialize the heap and generate a small root (large root) heap. The source code of Init method is as follows:

// A heap must be initialized before any of the heap operations
// can be used. Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// Its complexity is O(n) where n = h.Len().
//
func Init(h Interface) {
	// heapify
	n := h.Len()  // Gets the length of the data
	for i := n/2 - 1; i >= 0; i-- {  // From half the length to the 0th data, each position calls the down method. The function of the down method is to ensure that the heap is formed from this position down
		down(h, i, n)
	}
}

Next, look at the source code of down:

func down(h Interface, i0, n int) bool {
	i := i0  // The intermediate variable is stored for the first time to ensure the node position where the heap needs to be formed
	for {  // Dead cycle
		j1 := 2*i + 1  // Left child of node i
		if j1 >= n || j1 < 0 { // J1 < 0 after int overflow / / ensure that the left child does not cross the boundary
			break
		}
		j := j1 // Left child / / the intermediate variable j is first assigned to the left child, and then j will be assigned to the position of the smallest (largest) child among the left and right children
		if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
			j = j2 // = 2*i + 2  // right child
		}  // After that, j is assigned the position of the smallest (eldest) of the two children (the smallest or largest is determined by the definition in Less)
		if !h.Less(j, i) {
			break
		}  // If j is greater than (less than) i, the cycle is terminated
		h.Swap(i, j)  // Otherwise, swap the values of the i and j positions
		i = j  // Let i=j and continue the cycle to ensure that the number of children at j is the heap structure
	}
	return i > i0
}

This is the core code for building the heap. In fact, down does not completely guarantee that every node from a node down can maintain the characteristics of the heap. It can only ensure that the value of a node does not meet the properties of the heap. If the value does not meet the properties of the heap, exchange the value with its children until the value is placed in a suitable position to ensure that the value and its two children meet the properties of the heap.

However, if you call down through the Init loop, it will ensure that all nodes maintain the heap characteristics after initialization. This is because the value position of I: = n / 2 - 1 at the beginning of the loop will get the largest node with child nodes, and the node has only two children at most, and its child nodes are leaf nodes, If each node from this node to the front can guarantee the down feature, the whole list conforms to the nature of the heap.

Similarly, there is up when there is down. Up ensures that if a node does not guarantee the nature of the heap upward, it will be exchanged with the parent node until the node is placed in a specific location to ensure the nature of the heap. The code is as follows:

func up(h Interface, j int) {
	for {  // Dead cycle
		i := (j - 1) / 2 // Parent / / parent node of J node
		if i == j || !h.Less(j, i) {  // If it is out of bounds or the heap condition is met, the loop ends
			break
		}
		h.Swap(i, j)  // Otherwise, the node is swapped with the parent node
		j = i  // Continue checking the parent node until the root node
	}
}

The above two methods are the core methods. All the exposed methods are nothing more than the encapsulation of these two methods. Let's take a look at the source code of these methods:

func Push(h Interface, x interface{}) {
	h.Push(x)  // Put the newly inserted node last
	up(h, h.Len()-1)  // Ensure that the heap structure can be guaranteed on the newly inserted node network
}

func Pop(h Interface) interface{} {
	n := h.Len() - 1  // Exchange the last node with the first node, then re guarantee the heap structure from the root node, and finally throw out and return the data of the last node
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

func Remove(h Interface, i int) interface{} {
	n := h.Len() - 1  pop just remove Special circumstances, remove Yes i The node of the location is exchanged with the last node, and then it is guaranteed that i The heap structure is guaranteed from the node down and up. Finally, the data of the last node is thrown out and returned
	if n != i {
		h.Swap(i, n)
		down(h, i, n)
		up(h, i)
	}
	return h.Pop()
}

func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {  // After the value of node i changes, it is necessary to ensure the heap rebalancing. First call down to ensure the heap structure under the node. If there is location exchange, it is necessary to ensure the upward heap structure of the node. Otherwise, it is not necessary to ensure the heap structure upward. It is a small optimization
		up(h, i)
	}
}

The above is all the source code of heap in go. I won't post the full version of the source code. The above understanding is based on my personal understanding. If there is anything wrong, I hope to criticize and correct it.

4. Implement priority queue with heap

Since heap is used, implement a priority queue with heap. This function is a good function.
The source code is as follows:

package main

import (
	"container/heap"
	"fmt"
)

type Item struct {
	value    string // The data in the priority queue can be of any type. Here, use string
	priority int    // The priority of the node in the priority queue
	index    int    // index is the location of the node in the heap
}

// The priority queue needs to implement the heap interface
type PriorityQueue []*Item

// Bind Len method
func (pq PriorityQueue) Len() int {
	return len(pq)
}

// Bind the Less method, where the Less than sign is used, and the small root heap is generated
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

// Bind swap method
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index, pq[j].index = i, j
}

// Bind the put method and set the index to - 1 to identify that the data has been out of the priority queue
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	item.index = -1
	return item
}

// Bind push method
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

// Update the position of item s with modified priority and value in the priority queue
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

func main() {
	// Create nodes and design their priorities
	items := map[string]int{"twenty fen": 5, "Zhang San": 3, "son of a bitch": 9}
	i := 0
	pq := make(PriorityQueue, len(items)) // Create a priority queue and initialize it
	for k, v := range items {             // Put node in priority queue
		pq[i] = &Item{
			value:    k,
			priority: v,
			index:    i}
		i++
	}
	heap.Init(&pq) // Initialize heap
	item := &Item{ // Create an item
		value:    "Li Si",
		priority: 1,
	}
	heap.Push(&pq, item)           // Enter priority queue
	pq.update(item, item.value, 6) // Update item priority
	for len(pq) > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s index:%.2d\n", item.priority, item.value, item.index)
	}
}

Output results:
03:Zhang San index:-01
05:twenty fen index:-01
06:Li Si index:-01
09:son of a bitch index:-01