heap

Documentation

Index

• type Heap
  • func New(items []*Item) *Heap
  • func (h *Heap) Delete(name string) bool
  • func (h *Heap) Len() int
  • func (h *Heap) Peek() (*Item, bool)
  • func (h *Heap) Pop() *Item
  • func (h *Heap) Push(name string, priority int)
  • func (h *Heap) Search(name string) (int, bool)
  • func (h *Heap) Update(name string, newPriority int) bool
• type Item
  • func NewItem(name string, priority int) *Item
  • func (i *Item) Name() string
  • func (i *Item) Priority() int

Examples

• Heap

Types

type Heap

type Heap struct {
	// contains filtered or unexported fields
}

Heap is a data structure that implements a min-heap. Not thread-safe.

Although we could use workqueue.DelayingInterface for this, we don't need the concurrency guarantees that the workqueue package provides, and we should use a more straightforward implementation instead.

Example

ExampleHeap implements the test from container/heap.

package main

import (
	"fmt"

	"github.com/furiko-io/furiko/pkg/utils/heap"
)

func main() {
	hp := heap.New([]*heap.Item{
		heap.NewItem("banana", 3),
		heap.NewItem("apple", 2),
		heap.NewItem("pear", 4),
	})

	// Insert a new item and then modify its priority.
	hp.Push("orange", 1)
	hp.Update("orange", 5)

	// Take the items out; they arrive in increasing priority order.
	for hp.Len() > 0 {
		item := hp.Pop()
		fmt.Printf("%.2d:%s ", item.Priority(), item.Name())
	}
}

Output:

02:apple 03:banana 04:pear 05:orange

func New

func New(items []*Item) *Heap

New returns a new Heap.

func (*Heap) Delete

func (h *Heap) Delete(name string) bool

Delete an item from the heap.

func (*Heap) Len

func (h *Heap) Len() int

Len returns the length of the heap.

func (*Heap) Peek

func (h *Heap) Peek() (*Item, bool)

Peek an item from the heap.

func (*Heap) Pop

func (h *Heap) Pop() *Item

Pop an item from the heap.

func (*Heap) Push

func (h *Heap) Push(name string, priority int)

Push a new Item to the heap.

func (*Heap) Search

func (h *Heap) Search(name string) (int, bool)

Search returns the priority of an item in the heap.

func (*Heap) Update

func (h *Heap) Update(name string, newPriority int) bool

Update an item's priority in the heap.

type Item

type Item struct {
	// contains filtered or unexported fields
}

Item is a single object in priorityQueue.

func NewItem

func NewItem(name string, priority int) *Item

func (*Item) Name

func (i *Item) Name() string

Name returns the name of the item.

func (*Item) Priority

func (i *Item) Priority() int

Priority returns the priority of the item.