In-depth understanding of Golang's official container/heap usage

Opening

Golang's standard library container contains several common data structure implementations, which are actually very good learning materials. We can review the classic data structures and see how Golang's official team thinks.

container/list two-way linked list;
container/ring loop link list;
container/heap heap.

Today we will take a look at the source code of container/heap to learn how the official students design it and how we should use it as developers.

container/heap

Package heap provides heap operations for all types implemented. A heap is a tree. The value of each node of this tree is smaller than the value of its child nodes. The smallest value of the entire tree is located at the root, that is, the position of index 0.

Heap is a common way to implement a priority queue. In order to build a priority queue, when implementing the heap interface, the user needs to let the Less() method return the reverse order result, so that while using Push to add elements, the highest priority element in the queue can be removed through Pop.

heapis a common way to implement priority queues. The heap in Golang is the smallest heap and needs to meet two characteristics:

The value of a node in the heap is always no less than the value of its parent node;
The heap is always a completely binary tree.

Therefore, the root node is the smallest value in the heap.

There is a very interesting phenomenon. As you all know, Golang did not have generics before. As a strongly typed language, to implement general writing methods, [code generation] or [reflection] will generally be used.

As an official package, Golang hopes to provide you with a simple access method, and the official provides a good algorithm kernel, so everyone can access it. It uses the method of defining an interface that developers can implement.

In the container/heap package, we can find this Interface definition as soon as we start:

// The Interface type describes the requirements
// for a type using the routines in this package.
// Any type that implements it may be used as a
// min-heap with the following invariants (established after
// Init has been called or if the data is empty or sorted):
//
//	!(j, i) for 0 <= i < () and 2*i+1 <= j <= 2*i+2 and j < ()
//
// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use  and .
type Interface interface {
	
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

In addition to the two methods of heaping their own, Push and Pop, there is also a built-in:

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

Core Functions

Init

As developers, we have implemented container/ based on our own structure. How should we use it?

First, call it(h Interface)Method, pass into our implementation:

// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = ().
func Init(h Interface) {
	// heapify
	n := ()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

The heap must be initialized before any heap operation is performed. The Init operation is idempotent for heap invariants, and it can be called regardless of whether heap invariants is valid or not.

The complexity of the Init function is O(n) , where n equals ().

Pop/Push

As a heap, of course, you need to implement the two abilities of [insert] and [popup]. Here any is actually interface{}

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = ().
func Push(h Interface, x any) {
	(x)
	up(h, ()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = ().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) any {
	n := () - 1
	(0, n)
	down(h, 0, n)
	return ()
}

The Push function pushes an element with a value of x into the heap, and the complexity of the function is O(log(n)) .
The Pop function removes and returns the element with the minimum value from the heap based on the result of Less, which is equivalent to executing Remove(h, 0), and has a complexity of O(log(n)). (n equals () )

Remove

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = ().
func Remove(h Interface, i int) any {
	n := () - 1
	if n != i {
		(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return ()
}

The Remove function removes the element in the heap with an index of i, with a complexity of O(log(n))

Fix

Sometimes we change the elements on the heap and need to be reordered. This is the time to do it with Fix.

Note here:

【First modify the value of the element on index i and then execute Fix】
[First call Remove(h, i) and then use the Push operation to add the new value to the heap]

Both have the same effect. But Fix will cost less. The complexity is O(log(n)).

// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = ().
func Fix(h Interface, i int) {
	if !down(h, i, ()) {
		up(h, i)
	}
}

How to access

After implementing the above interface with the custom structure, first perform Init, and then call the Push / Pop / Remove / Fix we mentioned above. In fact, in most cases, the first two are enough. Let’s look at the two examples directly.

IntHeap

Let’s first look at a simple example, implementing a minimum heap based on integer.

First define your own type, int in this example, so skip this step;
Define a Heap type, here we usetype IntHeap []int；
Implement 5 methods of custom Heap type, three sorts, plus Push and Pop.

With the implementation, we can push the elements after Init. Here we initialize 2, 1, 5, and push 3. Finally, the printing result is perfectly output from small to large.

// This example demonstrates an integer heap built using the heap interface.
package main

import (
	"container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
	h := &IntHeap{2, 1, 5}
	(h)
	(h, 3)
	("minimum: %d\n", (*h)[0])
	for () > 0 {
		("%d ", (h))
	}
}

Output：
minimum: 1
1 2 3 5

Priority queue

The official also gave a method to implement a priority queue. We need a priority as the weight and add a value.

Value represents element value
Priority for sorting
Index value on pairs of Index elements, used to update elements.

// This example demonstrates a priority queue built using the heap interface.
package main

import (
	"container/heap"
	"fmt"
)

// An Item is something we manage in a priority queue.
type Item struct {
	value    string // The value of the item; arbitrary.
	priority int    // The priority of the item in the queue.
	// The index is needed by update and is maintained by the  methods.
	index int // The index of the item in the heap.
}

// A PriorityQueue implements  and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority > pq[j].priority
}

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

func (pq *PriorityQueue) Push(x any) {
	n := len(*pq)
	item := x.(*Item)
	 = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	 = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	 = value
	 = priority
	(pq, )
}

// This example creates a PriorityQueue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func main() {
	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	(&pq)

	// Insert a new item and then modify its priority.
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	(&pq, item)
	(item, , 5)

	// Take the items out; they arrive in decreasing priority order.
	for () > 0 {
		item := (&pq).(*Item)
		("%.2d:%s ", , )
	}
}


Output
05:orange 04:pear 03:banana 02:apple

Sort by timestamp

package util

import (
	"container/heap"
)

type TimeSortedQueueItem struct {
	Time  int64
	Value interface{}
}

type TimeSortedQueue []*TimeSortedQueueItem

func (q TimeSortedQueue) Len() int           { return len(q) }
func (q TimeSortedQueue) Less(i, j int) bool { return q[i].Time < q[j].Time }
func (q TimeSortedQueue) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }

func (q *TimeSortedQueue) Push(v interface{}) {
	*q = append(*q, v.(*TimeSortedQueueItem))
}

func (q *TimeSortedQueue) Pop() interface{} {
	n := len(*q)
	item := (*q)[n-1]
	*q = (*q)[0 : n-1]
	return item
}

func NewTimeSortedQueue(items ...*TimeSortedQueueItem) *TimeSortedQueue {
	q := make(TimeSortedQueue, len(items))
	for i, item := range items {
		q[i] = item
	}
	(&q)
	return &q
}

func (q *TimeSortedQueue) PushItem(time int64, value interface{}) {
	(q, &TimeSortedQueueItem{
		Time:  time,
		Value: value,
	})
}

func (q *TimeSortedQueue) PopItem() interface{} {
	if () == 0 {
		return nil
	}

	return (q).(*TimeSortedQueueItem).Value
}

Here we encapsulate a TimeSortedQueue containing a timestamp and our actual value. After implementation, the external NewTimeSortedQueue method can be exposed for initialization, and is called here.

At the same time, make a simple package and you can use it externally.

Summarize

The implementation of heap in Go language adopts a "template design pattern". When users implement custom heaps, they only need to implement functions in the interface, and then apply and other methods to achieve the desired functions. The heap management method is implemented by Go and stored in the heap.

This is the end of this article about in-depth understanding of Golang's official container/heap usage. For more information about Golang container/heap usage, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!