DEV Community

Discussion on: Hacktoberfest 2018 - Anyone looking for open source contributors?

View post
Collapse
 
theodesp profile image
Theofanis Despoudis • • Edited

Help is welcome for any Golang enthusiasts

theodesp / go-heaps

Reference implementations of heap data structures in Go

go-heaps

GoDoc License

Reference implementations of heap data structures in Go

Installation

$ go get -u github.com/theodesp/go-heaps

Contents

Heaps

  • Pairing Heap: A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance,

Usage

package main

import (
    pairingHeap "go-heaps/pairing"
    "fmt"
)

func main()  {
    heap := pairingHeap.NewWithIntComparator()
    heap.Insert(4)
    heap.Insert(3)
    heap.Insert(2)
    heap.Insert(5)

    fmt.Println(heap.DeleteMin()) // 2
    fmt.Println(heap.DeleteMin()) // 3
    fmt.Println(heap.DeleteMin()) // 4
    fmt.Println(heap.DeleteMin()) // 5
}

Complexity

Operation Pairing
FindMin Θ(1)
DeleteMin O(log n)
Insert Θ(1)
Find O(n)

LICENCE

Copyright © 2017 Theo Despoudis MIT license

View on GitHub