Documentation
¶
Overview ¶
Package heap is an alternative to the standard "heap" package. It implements a very similar function to the builtin heap(priority queue) package except the elements are not necessarily interface{}, but can be of any type.
The trick is to use the last element as the in/out place. Push/Pop/Remove are replaced with PushLast/PopToLast/RemoveToLast, respectively.
A heap with int value can be easily implemented as follow:
type IntHeap []int
func (h *IntHeap) Pop() int {
heap.PopToLast((*sort.IntSlice)(h))
res := (*h)[len(*h) - 1]
*h = (*h)[:len(*h) - 1]
return res
}
func (h *IntHeap) Push(x int) {
*h = append(*h, x)
heap.PushLast((*sort.IntSlice)(h))
}
Use of the IntHeap:
hp := IntHeap{3, 1, 5}
heap.Init(sort.Interface(h))
hp.Push(4)
...
value := hp.Pop()
PushLastF/PopToLastF/RemoveToLastF takes funcs other than sort.Interface as the argument. E.g., a heap with type T value can be implemented as follow:
type THeap []T
func (h *THeap) Pop() T {
heap.PopToLastF(len(*h), func(i, j int) bool {
ti, tj := (*h)[i], (*h)h[j]
// return whether ti < tj
}, func(i, j int) {
(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
})
res := (*h)[len(*h) - 1]
*h = (*h)[:len(*h) - 1]
return res
}
func (h *THeap) Push(x T) {
*h = append(*h, x)
heap.PushLastF(len(*h), func(i, j int) bool {
ti, tj := (*h)[i], (*h)h[j]
// return whether ti < tj
}, func(i, j int) {
(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
})
}
Index ¶
- func Fix(h sort.Interface, index int)
- func FixF(Len int, Less func(i, j int) bool, Swap func(i, j int), index int)
- func Init(h sort.Interface)
- func InitF(Len int, Less func(i, j int) bool, Swap func(i, j int))
- func PopToLast(h sort.Interface)
- func PopToLastF(Len int, Less func(i, j int) bool, Swap func(i, j int))
- func PushLast(h sort.Interface)
- func PushLastF(Len int, Less func(i, j int) bool, Swap func(i, j int))
- func RemoveToLast(h sort.Interface, i int)
- func RemoveToLastF(Len int, Less func(i, j int) bool, Swap func(i, j int), i int)
- type Float64s
- type Interfaces
- type Ints
- type Strings
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Fix ¶
Fix re-establishes the heap ordering after the value of the element at the index has changed. Changing the value of the element at the index and then calling Fix is equivalent to, but less expensive than, calling RemoveToLast(h, index) followed by a PushLast. The complexity is O(log(N)), where N = h.Len().
func Init ¶
Init heapifies a non-empty array defined by the sort.Interface. The complexity is O(N), where N = h.Len().
func PopToLast ¶
Pop removes the minimum element (according to Less) from the heap and place it as the last element of the heap. The complexity is O(log(N)), where N = h.Len().
Same as Remove(h, 0).
NOTE You need to remove the last element after calling to this method.
func PopToLastF ¶
Similar to PopToLast but with interface provided by funcs.
func PushLast ¶
Push pushes the last element of the heap, which was not considered as part of the heap, onto the heap. The complexity is O(log(N)), where N = h.Len().
NOTE You need to append the element to be pushed as the last element before calling to this method.
func RemoveToLast ¶
Remove removes the element at index i from the heap and place it at the last element of the heap.
The complexity is O(log(n)) where n = h.Len().
NOTE You need to remove the last element after calling to this method.
Types ¶
type Float64s ¶
type Float64s struct {
// contains filtered or unexported fields
}
A heap for strings. The pointer to the zero value of Float64s is a heap with default less func which compares string values on the natual order. Use NewFloat64s to customize less func and initial capacity.
func NewFloat64s ¶
NewFloat64s returns a *Float64s with customized less func and initial capacity.
type Interfaces ¶
type Interfaces interface {
// Len returns the number of elements in the current heap.
Len() int
// Push inserts an element to the heap.
Push(x interface{})
// Pop removes the top element from the heap and returns it.
Pop() interface{}
// PopAll pops and returns all elements of the heap in reverse order.
PopAll() []interface{}
// Peek returns the top most element. It panics if the heap is empty.
Peek() interface{}
// TopNPush inserts an element to the heap if the heap does not reach its
// capacity. Otherwise, if the top element is less then the new element
// the top element is removed and the new one is inserted.
// This method is used to generate a top N largest elements where N is
// the capacity of the heap.
TopNPush(x interface{})
// TopNPopAll is similar to PopAll but keep the capacity of the heap
// unchanged.
TopNPopAll() []interface{}
}
A heap for interface{}. Use NewInterfaces to create an instance.
func NewInterfaces ¶
func NewInterfaces(less func(x, y interface{}) bool, cap int) Interfaces
NewInterfaces returns an instance of Interfaces with a customized less func and the initial capacity.
type Ints ¶
type Ints struct {
// contains filtered or unexported fields
}
A heap for ints. The pointer to the zero value of Ints is a heap with default less func which compares int values on the natual order. Use NewInts to customize less func and initial capacity.
type Strings ¶
type Strings struct {
// contains filtered or unexported fields
}
A heap for strings. The pointer to the zero value of Strings is a heap with default less func which compares string values on the natual order. Use NewStrings to customize less func and initial capacity.
func NewStrings ¶
NewStrings returns a *Strings with a customized less func and the initial capacity.
Source Files