How to implement min-heap in Go language

Minimum heap is a data structure that can quickly find the smallest element. In Go language, we can use the heap package to implement minimum heap. In this article, we will detail how to implement min-heap in Go language.

What is a minimum heap?

Minimum heap is a binary tree structure that satisfies the following two conditions:

1. The value of the parent node is less than or equal to the value of its child node.
2. Each level is filled from left to right.

For example, the following is a minimum heap:

      2
    /   \
   5     3
  / \   / \
 7   6 8   4

In a minimum heap, the root node is always the smallest element, so the time complexity of finding the minimum value is O(1) . The time complexity of the insertion and deletion operations of the minimum heap is O(log n).

How to implement minimum heap?

In the Go language, we can use the heap package to implement a minimum heap. The heap package provides the following three methods to implement the minimum heap:

1. Init: Initialize an empty minimum heap.
2. Push: Insert elements into the min-heap.
3. Pop: Remove and return the smallest element from the min-heap.

First, we need to define a data structure to store elements. In this article, we will use int type as elements. Since we need to convert the int type to the heap.Interface type, we need to implement three methods of the heap.Interface interface: Len, Less and Swap.

type MinHeap []int

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

In the above code, we define a MinHeap type and implement the Len, Less and Swap methods. The Len method returns the number of elements in the minimum heap, the Less method compares the sizes of two elements, and the Swap method exchanges the positions of two elements.

Next, we need to implement the minimum heap initialization method. We can use the heap.Init function to initialize an empty min-heap.

h := &MinHeap{}
heap.Init(h)

Now, we have initialized an empty min-heap. Next, we can use the heap.Push function to insert elements.

heap.Push(h, 2)
heap.Push(h, 5)
heap.Push(h, 3)
heap.Push(h, 7)
heap.Push(h, 6)
heap.Push(h, 8)
heap.Push(h, 4)

In the above code, we use the heap.Push function to insert elements into the min-heap.

We can also use the heap.Pop function to delete and return the smallest element.

for h.Len() > 0 {
     fmt.Printf("%d ", heap.Pop(h))
}

In the above code, we use loop and heap.Pop function to output all elements in the min-heap.

Complete code:

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int

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

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

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

func main() {
    h := &MinHeap{}
    heap.Init(h)

    heap.Push(h, 2)
    heap.Push(h, 5)
    heap.Push(h, 3)
    heap.Push(h, 7)
    heap.Push(h, 6)
    heap.Push(h, 8)
    heap.Push(h, 4)

    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

In the above code, in addition to implementing the Len, Less and Swap methods, we also implement the Push and Pop methods. The Push method inserts elements into the min-heap, and the Pop method removes and returns the smallest element from the min-heap.

Summary

This article introduces how to implement minimum heap in Go language. By using the functions provided by the heap package, we can quickly implement a min-heap with O(log n) time complexity when inserting and deleting elements. If you need to implement other types of heap, please consult the documentation of the heap package.

The above is the detailed content of How to implement min-heap in Go language. For more information, please follow other related articles on the PHP Chinese website!