keyheap

Documentation

Overview

Package keyheap implements a library for a simple heap that allows peeking and popping from the middle based on a Key() in the stored interface.

Example (New)

heap := New()
fmt.Println(heap)

Output:

KeyHeap([])

Example (NewFromItems)

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

fmt.Println(q)

Output:


KeyHeap([
        {0:thing 3: priority=999}
        {1:thing 5: priority=1002}
        {2:thing 1: priority=1000}
        {3:thing 4: priority=1005}
        {4:thing 2: priority=1004}
        {5:thing 6: priority=1001}
        {6:thing 7: priority=1003}
     ])

Index

• type Item
• type KeyHeap
  • func New() *KeyHeap
  • func NewFromItems(items []Item) *KeyHeap
  • func (q *KeyHeap) Len() int
  • func (q *KeyHeap) Peek() Item
  • func (q *KeyHeap) PeekAt(idx int) Item
  • func (q *KeyHeap) PeekByKey(key int64) Item
  • func (q *KeyHeap) Pop() Item
  • func (q *KeyHeap) PopAt(idx int) Item
  • func (q *KeyHeap) PopByKey(key int64) Item
  • func (q *KeyHeap) PopRandomConstrained(maxPriority int64) Item
  • func (q *KeyHeap) Push(item Item)
  • func (q *KeyHeap) String() string

Examples

• Package (New)
• Package (NewFromItems)
• KeyHeap.Peek
• KeyHeap.PeekAt
• KeyHeap.PeekByKey
• KeyHeap.Pop
• KeyHeap.PopAt
• KeyHeap.PopByKey
• KeyHeap.Push

Types

type Item

type Item interface {
	// Priority is used to determine which element (lowest priority) is at the
	// top of the heap.
	Priority() int64

	// Key is used to look up individual items inside of the heap.
	Key() int64
}

type KeyHeap

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

func New

func New() *KeyHeap

New creates a new empty KeyHeap.

func NewFromItems

func NewFromItems(items []Item) *KeyHeap

NewFromItems creates a KeyHeap from a slice of Item.

func (*KeyHeap) Len

func (q *KeyHeap) Len() int

Len returns the size of the heap.

func (*KeyHeap) Peek

func (q *KeyHeap) Peek() Item

Peek returns the top element in the heap (with the smallest Priority()), or nil if the heap is empty.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

fmt.Println(q.Peek())

Output:


thing 3: priority=999

func (*KeyHeap) PeekAt

func (q *KeyHeap) PeekAt(idx int) Item

PeekAt finds the item at index idx in the heap and returns it. Returns nil if idx is out of bounds.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

fmt.Println(q.PeekAt(3))

Output:


thing 4: priority=1005

func (*KeyHeap) PeekByKey

func (q *KeyHeap) PeekByKey(key int64) Item

PeekByKey finds the item with the given Key() and returns it, or nil if not found.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

fmt.Println(q.PeekByKey(5))

Output:


thing 5: priority=1002

func (*KeyHeap) Pop

func (q *KeyHeap) Pop() Item

Pop removes the Item with the lowest Priority() from the KeyHeap.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

// Pop the lowest priority item.
thing := q.Pop()
fmt.Println(thing)
fmt.Println(q)

Output:


thing 3: priority=999
KeyHeap([
        {0:thing 1: priority=1000}
        {1:thing 5: priority=1002}
        {2:thing 6: priority=1001}
        {3:thing 4: priority=1005}
        {4:thing 2: priority=1004}
        {5:thing 7: priority=1003}
     ])

func (*KeyHeap) PopAt

func (q *KeyHeap) PopAt(idx int) Item

PopAt removes an element from the specified index in the heap in O(log(n)) time.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

// Pop the lowest priority item.
thing := q.PopAt(4)
fmt.Println(thing)
fmt.Println(q)

Output:


thing 2: priority=1004
KeyHeap([
        {0:thing 3: priority=999}
        {1:thing 5: priority=1002}
        {2:thing 1: priority=1000}
        {3:thing 4: priority=1005}
        {4:thing 7: priority=1003}
        {5:thing 6: priority=1001}
     ])

func (*KeyHeap) PopByKey

func (q *KeyHeap) PopByKey(key int64) Item

PopByKey finds the item with the given Key() and returns it, removing it from the data structure.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

fmt.Println(q.PopByKey(2))
fmt.Println(q)

Output:


thing 2: priority=1004
KeyHeap([
        {0:thing 3: priority=999}
        {1:thing 5: priority=1002}
        {2:thing 1: priority=1000}
        {3:thing 4: priority=1005}
        {4:thing 7: priority=1003}
        {5:thing 6: priority=1001}
     ])

func (*KeyHeap) PopRandomConstrained

func (q *KeyHeap) PopRandomConstrained(maxPriority int64) Item

PopRandomConstrained walks the heap randomly choosing a child until it either picks one or runs out (and picks the last one before the maxPriority). If maxPriority <= 0, then there is no constraint. Note that this greatly favors items near the top, because the probability of traversing the tree very far quickly gets vanishingly small. There are undoubtedly other interesting approaches to doing this.

func (*KeyHeap) Push

func (q *KeyHeap) Push(item Item)

Push adds an Item to the heap.

Example

q := NewFromItems([]Item{
	&thing{1, 1000},
	&thing{2, 1004},
	&thing{3, 999},
	&thing{4, 1005},
	&thing{5, 1002},
	&thing{6, 1001},
	&thing{7, 1003},
})

q.Push(&thing{8, 998})
fmt.Println(q)

Output:


KeyHeap([
        {0:thing 8: priority=998}
        {1:thing 3: priority=999}
        {2:thing 1: priority=1000}
        {3:thing 5: priority=1002}
        {4:thing 2: priority=1004}
        {5:thing 6: priority=1001}
        {6:thing 7: priority=1003}
        {7:thing 4: priority=1005}
     ])

func (*KeyHeap) String

func (q *KeyHeap) String() string

String formats this heap into a string.