Menu Close

Go – Heap data structure in go

Here, We are going to learn about heap data structure in go golang. We can achieve this by using heap package.

The minimum element in the tree is the root and the index of root is 0.

How to import heap package in go golang:

 import "container/heap"

Example:

package main

import (

  "container/heap"
  "fmt"

)

// An TestHeap is a min-heap of ints.

type TestHeap []int

func (h TestHeap) Len() int {

 return len(h)

}

func (h TestHeap) Less(i, j int) bool {

  return h[i] < h[j]

}

func (h TestHeap) Swap(i, j int) {

  tmp := h[i]

  h[i] = h[j]

  h[j] = tmp

}

func (h *TestHeap) Push(i interface{}) {

  // Push and Pop use pointer receivers because 
  // they modify the slice's length, 
  // not just its contents.

  *h = append(*h, i.(int))

}

func (h *TestHeap) Pop() interface{} {

  pre := *h

  length := len(pre)

  x := pre[length - 1]

  *h = pre[0 : length - 1]

  return x
}

func main() {

  h := &TestHeap{9, 2, 10, 1}

  heap.Init(h)

  heap.Push(h, 4)

  fmt.Printf("minimum: %d\n", (*h)[0])

  for h.Len() > 0 {

    fmt.Printf("%d ", heap.Pop(h))

  }

}

Output:

minimum: 1 

1 2 4 9 10

Heap package has functions which are used in implementation of heap data structure.

  • Fix()
  • Init()
  • Pop()
  • Push()
  • Remove()
  • type interface

To learn more about golang, Please refer given below link.

https://www.techieindoor.com/go-lang-tutorial/

References:

 https://golang.org/doc/
 https://golang.org/pkg/
 https://golang.org/pkg/fmt/

Posted in golang, heap

Leave a Reply

Your email address will not be published.

Contact Us