Documentation
¶
Overview ¶
Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.
The minimum element in the tree is the root, at index 0.
A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.
Package sort provides primitives for sorting slices and user-defined collections.
Index ¶
- func HeapFix(h heapSlice, i int)
- func HeapInit(h heapSlice)
- func HeapPop(h *heapSlice) heapElem
- func HeapPush(h *heapSlice, x heapElem)
- func HeapRemove(h *heapSlice, i int) heapElem
- func Merge(col []*vector.Vector, src *[]uint16)
- func Multiplex(col []*vector.Vector, src []uint16)
- func Shuffle(col *vector.Vector, idx []uint32)
- func Sort(col *vector.Vector, idx []uint32)
- func SortStable(data sortSlice)
- func SortUnstable(data sortSlice)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func HeapFix ¶
func HeapFix(h heapSlice, i int)
Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a Push of the new value. The complexity is Operator(log n) where n = len(h).
func HeapInit ¶
func HeapInit(h heapSlice)
Init establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is Operator(n) where n = len(h).
func HeapPop ¶
func HeapPop(h *heapSlice) heapElem
Pop removes and returns the minimum element (according to Less) from the heap. The complexity is Operator(log n) where n = len(h). Pop is equivalent to Remove(h, 0).
func HeapPush ¶
func HeapPush(h *heapSlice, x heapElem)
Push pushes the element x onto the heap. The complexity is Operator(log n) where n = len(h).
func HeapRemove ¶
func HeapRemove(h *heapSlice, i int) heapElem
Remove removes and returns the element at index i from the heap. The complexity is Operator(log n) where n = len(h).
func SortStable ¶
func SortStable(data sortSlice)
Stable sorts data while keeping the original order of equal elements.
It makes one call to data.Len to determine n, Operator(n*log(n)) calls to data.Less and Operator(n*log(n)*log(n)) calls to data.Swap.
func SortUnstable ¶
func SortUnstable(data sortSlice)
Sort sorts data. It makes one call to data.Len to determine n and Operator(n*log(n)) calls to data.Less and data.Swap. The sort is not guaranteed to be stable.
Types ¶
This section is empty.
Source Files