Preface

The standard library container of golang provides an implementation of heap. This article briefly analyzes how it is implemented and how to use it.

heap

Taking minheap minimal binomial heap as an example, the heap has the following properties.

  • Any node is smaller than all its children, and the smallest node is at the root of the heap (heap orderliness)
  • The heap is a complete tree: i.e., all nodes in all layers except the bottom layer are filled with elements, and the bottom layer is filled from left to right as much as possible.
  • Since a heap is a complete binary tree, it can be represented as an ordered array, as follows

ordered array

source code analysis

The heap of the standard library is an interface, so the developer needs to implement the relevant interfaces (5 in total, including 3 of sort.Interface). During the source code analysis, special attention was paid to the embedding of these public interfaces.

1
2
3
4
5

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

Recall that the minheap insertion/deletion process.

  • When inserting Push an element into the minheap, insert this element into the last node of the rightmost subtree, and then call up to adjust upward to ensure the minimum heap property.
  • When removing the top element (the smallest) from the minheap, swap it with the last node of the right subtree, then Pop the last node, then call down on the root node to adjust it downward to ensure the minimum heap property.
  • Fetching data from any position of the minheap is similar to the above.

Main method analysis

  1. Init method

    Init is the method to initialize the heap, the key is in the heap.down method.

    • In the Init method, the position is adjusted so that the first 1 element is n/2-1, in line with the characteristics of minheap; the last position is 0 at the top of the heap to ensure that no element is left out.
    • If i is smaller than its children, then i is swapped with the smaller of the two children (j in the code); the child j is then compared with its children, and swapped until the end of the array, or the element to be compared is is smaller than both of its children, the current heap.down loop is jumped out.
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    // 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()
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)
    }
}

// Given the type, the index of the element to be adjusted in the array and the length of the heap
// Sink the element to the appropriate position in the subtree corresponding to the element, so that the subtree is the smallest heap
func down(h Interface, i0, n int) bool {
    i := i0
    for {
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
            break
        }
        j := j1 // left child
        if j2 := j1 + 1; j2 <n && h.Less(j2, j1) {
            j = j2 // = 2*i + 2 // right child
        }
        if !h.Less(j, i) {
        // The minimum heap requirement has been met, exit
            break
        }
        h.Swap(i, j)
        i = j
    }
    return i > i0
}

  2. Push method

    The Push method ensures that when a new element is inserted, the sequential array h remains a heap; as described above, the x element is inserted at the end of the array, and then the up method is called to adjust it from the bottom up to satisfy the heap property.

    The heap.up method is also easy to understand: find the parent node (i) of the element j according to this (for loop), and if j is smaller than the parent node i, swap the two nodes and continue comparing to the parent node further up the hierarchy until the root node, or the element j is larger than the parent node i (the adjustment is done, no need to continue).

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

func up(h Interface, j int) {
    for {
        i := (j - 1) / 2 // parent
        if i == j || !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        j = i
    }
}

  3. Pop method

    The heap.Pop method takes out the data from the top position of the heap (minheap is the minimum), and after taking the data, the heap is definitely not balanced. So the usual practice is to swap the root node (0 position) with the elements of the last node, and adjust the elements of the new root node (the previous last element) down to the appropriate position from top to bottom to satisfy the minheap requirement.

    Finally, the user-defined Pop function is called to get the last element.

    There is a fundamental difference between the Pop method of the heap package and the Pop method of the user-defined implementation, where the user’s Pop method is only used to get the data.

    1
2
3
4
5
6
7
8
9

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

  4. Remove method

    The Remove method provides an implementation to remove the index element at the specified position, i.e. swap the node i to be removed with the last node n, and then sink or float the new node i to the appropriate position (in layman’s terms, due to new data adjustments, the original last position has risen to where it should not be, and the element needs to be adjusted, first all the way down to the end, and then all the way up to the final position).

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

  5. Fix method

    The meaning of the Fix method is in the priority queue scenario (rebalancing the heap after a change in data from the i position, the priority queue will use this method).

    1
2
3
4
5
6
7
8
9

    // 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 = h.Len().
func Fix(h Interface, i int) {
    if !down(h, i, h.Len()) {
        up(h, i)
    }
}

heap instantiation

The following implements a heap using the slice structure of []int, and note that the call is made using the methods of the heap package.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

type IntHeap []int

func main() {
    h := &IntHeap{2, 1, 5, 13,11, 4, 3, 7, 9, 8, 0}
    heap.Init(h)                                // Heaping array slices
    fmt.Println(*h)
    fmt.Println(heap.Pop(h))                    // Call pop 0 to return the top smallest element removed
    heap.Push(h, 6)                             // Add an element to the heap for heapification
    for len(*h) > 0 {
      fmt.Printf("%d \n", heap.Pop(h))
    }
}

func (h IntHeap) Len() int { return len(h) }

func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }   //minheap

func (h IntHeap) Swap(i, j int) {
        h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    // The result of swapping the position of the top minor heap element with the last element in a heap sort
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// Implement the Push method to insert new elements
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

Usage scenarios for heap

  1. timer
  2. priority queue
  3. heap sorting

Summary

To use the standard library’s heap, you need to specify these items.

  • Define your own interface that implements the methods needed by the heap.
  • Note that the methods of package, and the methods of structs, although with the same name, have completely different functions.
  • The usage scenarios of heap.Fix and heap.Remove methods.