pyramid

README

Pyramid

Fast generic Heap in Golang. Create your heap with any type of data. Set your compression function to sort your data with any field that you want. Push, Pop and Update your data in heap without any problems.

How to use?

Get pyramid package.

go get github.com/amirhnajafiz/pyramid

Example

Creating a max-heap of integers type.

package main

import (
	"fmt"

	"github.com/amirhnajafiz/pyramid"
)

func main() {
	h := pyramid.NewHeap[int](func(a int, b int) bool {
		return a > b
	})

	h.Push(2)
	h.Push(12)
	h.Push(4)
	h.Push(90)
	h.Push(20)

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

Creating a min-heap of custome data type.

type Data struct {
	Priority int
	Data     string
}

func main() {
	h := pyramid.NewHeap[Data](func(a Data, b Data) bool {
		return a.Priority < b.Priority
	})

	for i := 0; i < 10; i++ {
		h.Push(Data{Priority: i, Data: fmt.Sprintf("data: %d", i+1)})
	}

	for h.Length() > 0 {
		fmt.Printf("%s\n", h.Pop().(Data).Data)
	}
}

Updating a reference

You can update any item in the list, also you can define a equal function to check the equality of your objects.

special := 675

h.Push(special)

for i := 2; i < 100; i++ {
    h.Push(i)
}

h.Update(special, 0, func(a int, b int) bool {
    return a == b
})

Load test

If we have 10000 items, and we want to update them 1 Million times, it would only take 12 seconds:

go run load-test/update/main.go -push 10000 -update 1000000

testing: 10000 numbers
start: Oct 16 14:42:34.752
done: Oct 16 14:42:52.064
final size: 10000
min: 2

Documentation

Index

• type Heap
  • func NewHeap[T any](compareFunction compareFunction[T]) Heap[T]
  • func (h *Heap[T]) Length() int
  • func (h *Heap[T]) Pop() any
  • func (h *Heap[T]) Push(value any)
  • func (h *Heap[T]) Update(old any, new any, ef equalFunction[T])
• type Queue
  • func (pq Queue[T]) Len() int
  • func (pq Queue[T]) Less(i, j int) bool
  • func (pq *Queue[T]) Pop() any
  • func (pq *Queue[T]) Push(x any)
  • func (pq Queue[T]) Swap(i, j int)

Types

type Heap

type Heap[T any] struct {
	// contains filtered or unexported fields
}

Heap type which manages the heap list of any type.

func NewHeap

func NewHeap[T any](compareFunction compareFunction[T]) Heap[T]

NewHeap creates a new heap of any type.

func (*Heap[T]) Length

func (h *Heap[T]) Length() int

Length heap length.

func (*Heap[T]) Pop

func (h *Heap[T]) Pop() any

Pop items from list.

func (*Heap[T]) Push

func (h *Heap[T]) Push(value any)

Push items to heap.

func (*Heap[T]) Update

func (h *Heap[T]) Update(old any, new any, ef equalFunction[T])

Update the queue list.

type Queue

type Queue[T any] struct {
	// contains filtered or unexported fields
}

Queue is a list of items.

func (Queue[T]) Len

func (pq Queue[T]) Len() int

Len returns the Queue size.

func (Queue[T]) Less

func (pq Queue[T]) Less(i, j int) bool

Less comparator function.

func (*Queue[T]) Pop

func (pq *Queue[T]) Pop() any

Pop extract one item from Queue list.

func (*Queue[T]) Push

func (pq *Queue[T]) Push(x any)

Push new items to Queue list.

func (Queue[T]) Swap

func (pq Queue[T]) Swap(i, j int)

Swap function for Queue.