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 (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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type KeyHeap ¶
type KeyHeap struct {
// contains filtered or unexported fields
}
func NewFromItems ¶
NewFromItems creates a KeyHeap from a slice of Item.
func (*KeyHeap) Peek ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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} ])
Source Files