README- UAhoCorasick
- UArcCache
- UArenaTree
- UBiMap
- UBitSet
- UBitVec
- UBloomFilter
- UBloomOptions
- UBoyerMoore
- UCacheStats
- UChainMap
- UCombinations
- UCombinationsWithReplacement
- UCountMinSketch
- UCounter
- UCuckooFilter
- UCuckooOptions
- UDaryHeap
- UDefaultMap
- UDenseSlotMap
- UDisjointSet
- UDisjointSetMap
- UExpiringCache
- UFenwick
- UFibonacciHeap
- UFlatMap
- UFlatMultiMap
- UFlatMultiSet
- UFlatSet
- UGapBuffer
- UGrayCode
- UGrowth
- UHeapKey
- UHyperLogLog
- UIndexHeap
- UIndexMap
- UIndexSet
- UIntervalKey
- UIntervalTree
- UJoinEntry
- UKmp
- ULazySegmentTree
- ULfuCache
- ULinkedList
- ULruCache
- UMatch
- UMinMaxHeap
- UMultiMap
- UMultiSet
- UOpcode
- UOrder
- UOrderStatisticTree
- UOverflow
- UOverlap
- UPairingHeap
- UPermutations
- UPhfBuild
- UPhfBuilder
- UPhfLayout
- UPhfMap
- UPhfOptions
- UPhfOrderedMap
- UPhfOrderedSet
- UPhfSet
- UPosition
- UPowerset
- UProduct
- URadixHeap
- URadixTree
- URangeMap
- URangeSet
- URefused
- URingBuffer
- URope
- URopeBuilder
- URopeView
- USecondaryMap
- USegmentTree
- USequenceMatcher
- USequenceMatcherOptions
- USkipList
- USkipListOptions
- USlab
- USlotKey
- USlotMap
- USortedMultiMap
- USortedMultiSet
- USparseSet
- USuffixArray
- USuffixAutomaton
- UTDigest
- UThetaSketch
- UTreap
- UTreeId
- UTrie
moonbitstack/moonstl/heap does not have a README file
DaryHeap
A d-ary heap: a heap laid out in a contiguous array where every node has up
to arity children.
A binary heap does one comparison per level; a 4-ary heap does three but
halves the number of levels, and the children of one node sit next to each
other in memory, so a wider heap usually wins on modern caches. arity: 4 is
Boost.Heap's default for d_ary_heap.
The heap is a multiset: it does not remove duplicates, and its iteration
order is the internal array order, which is only partially ordered. Use
into_sorted_array when the order matters.
test {
let heap : @heap.DaryHeap[Int32] = try! @heap.DaryHeap::new()
heap.push(3)
heap.push(1)
heap.push(2)
assert_true(heap.peek() == Some(1))
assert_true(heap.pop() == Some(1))
assert_true(heap.length() == 2)
}DaryHeap::copy
A copy that shares no storage with the original; the comparator is shared
because it is a pure function of two elements.
DaryHeap::from_array
Builds a heap from items in O(n), by sifting down from the last parent
rather than pushing one at a time.
test {
let heap : @heap.DaryHeap[Int32] = try! @heap.DaryHeap::from_array([
5, 1, 4, 1, 3,
])
assert_true(heap.into_sorted_array() == [1, 1, 3, 4, 5])
}DaryHeap::from_array_by
Builds a heap ordered by cmp from items in O(n).
DaryHeap::from_iter
Builds a heap from an iterator in O(n log n).
DaryHeap::from_iter_by
Builds a heap ordered by cmp from an iterator.
DaryHeap::hash_combine
DaryHeap::into_sorted_array
Drains the heap into an array in pop order, leaving it empty.
test {
let heap : @heap.DaryHeap[Int32] = try! @heap.DaryHeap::from_array([3, 1, 2])
assert_true(heap.into_sorted_array() == [1, 2, 3])
assert_true(heap.is_empty())
}DaryHeap::is_empty
Whether the heap holds no elements.
DaryHeap::iter
The elements in the heap's internal array order, which is only partially
ordered.
DaryHeap::length
The number of elements the heap holds.
DaryHeap::new
Builds a min or max heap ordered by T : Compare.
arity is the number of children a node has and has to be at least 2;
anything smaller is refused because it does not describe a tree.
DaryHeap::new_by
Builds a min heap ordered by cmp, which has to return a negative number
when its first argument has to be popped first.
Use this for an ordering Compare cannot express — a case-insensitive key, a
field of a record, a reversed priority — rather than wrapping the element.
DaryHeap::peek
The element a pop would return, without removing it, in O(1).
DaryHeap::pop
Removes and returns the first element in O(log_d n), or None when the heap
is empty.
DaryHeap::push
Adds one element in O(log_d n).
test {
let heap : @heap.DaryHeap[Int32] = try! @heap.DaryHeap::new()
heap.push(2)
heap.push(1)
assert_true(heap.peek() == Some(1))
}DaryHeap::push_pop
Pushes value and pops the first element in one sift, which is Python's
heappushpop: the result is value itself when it would be popped straight
away, so a bound on a stream costs no tree update.
On an empty heap this is a push that returns None.
DaryHeap::replace
Removes the first element and puts value in its place in one sift down,
which is cheaper than pop followed by push. Returns the element removed.
On an empty heap this is a plain push that returns None.
DaryHeap::to_array
The elements in the heap's internal array order. Use into_sorted_array for
the order the heap pops in.
FibonacciHeap
A Fibonacci heap: roots and children sit in circular doubly linked lists,
so an insert only splices one node in, a meld only joins two lists, and a
decrease_key only cuts one subtree loose — each of them constant amortised
time. The price is paid on pop, which consolidates the roots by degree.
test {
let heap : @heap.FibonacciHeap[Int32] = @heap.FibonacciHeap::new()
let a = heap.insert(5)
let _ = heap.insert(2)
let _ = heap.insert(8)
assert_true(heap.peek() == Some(2))
assert_true(heap.decrease_key(a, 1))
assert_true(heap.pop() == Some(1))
}FibonacciHeap::contains
FibonacciHeap::decrease_key
Lowers the key of an entry that is already in the heap: a node that drops
below its parent is cut loose, which costs nothing to undo later because the
pop consolidates anyway. Refuses a value that is not a decrease.
FibonacciHeap::insert
FibonacciHeap::into_sorted_array
FibonacciHeap::merge
FibonacciHeap::remove_at
FibonacciHeap::update
Replaces the value whatever its direction: a node whose value no longer fits
under its parent is cut loose and the ancestors are repaired as a
decrease_key would repair them.
HeapKey
pub(all) struct HeapKey[T] {
index : Int
generation : UInt
}A stable handle to one entry of an addressable heap.
index names the entry's slot and generation the state that slot was in
when the handle was issued. A slot is reused after its entry is removed and
the generation is then bumped, so a handle kept past a removal names nothing
and every method taking one reports a miss instead of reaching the element
that took the slot. The type parameter names the element type the handle came
from, which keeps a handle from one heap type from being passed to another;
it holds no data.
HeapKey::from_json
IndexHeap
A binary heap whose entries are addressed by HeapKey: an update or a
remove_at reaches one element without searching, because every slot knows
its position in the heap array and every position knows its slot.
test {
let heap : @heap.IndexHeap[Int32] = @heap.IndexHeap::new()
let a = heap.insert(5)
let b = heap.insert(1)
assert_true(heap.update(a, 0))
assert_true(heap.peek() == Some(0))
assert_true(heap.remove_at(b) == Some(1))
assert_true(heap.length() == 1)
}IndexHeap::insert
Stores value and returns the handle that addresses it.
IndexHeap::into_sorted_array
The elements in pop order, emptying the heap.
MinMaxHeap
A double-ended priority queue: both the smallest and the largest element are
one comparison away, and both can be popped in logarithmic time. The array
alternates min levels and max levels, so the smallest is at the root and the
largest is one of its two children.
test {
let heap : @heap.MinMaxHeap[Int32] = @heap.MinMaxHeap::new()
for value in [5, 1, 9, 3, 7] {
heap.push(value)
}
assert_true(heap.peek_min() == Some(1))
assert_true(heap.peek_max() == Some(9))
assert_true(heap.pop_min() == Some(1))
assert_true(heap.pop_max() == Some(9))
}Order
Which end of the order a heap pops from.
Min pops the element that compares smallest and is what Python's heapq
and Java's PriorityQueue do; Max pops the largest and is what C++ and
core's PriorityQueue do. The two are one comparator apart, so the
direction is a value rather than a second type.
PairingHeap
A heap of linked nodes: every node keeps its children in a list and a meld
only links two roots, so insert and meld are constant time and a pop pays
for the pairwise merging of the children it uncovers. Its update and
remove_at reach a node through a HeapKey and detach it without a search,
which is what a scheduler that cancels timers needs.
test {
let heap : @heap.PairingHeap[Int32] = @heap.PairingHeap::new()
let a = heap.insert(5)
let b = heap.insert(2)
let _ = heap.insert(9)
assert_true(heap.peek() == Some(2))
assert_true(heap.update(a, 1))
assert_true(heap.peek() == Some(1))
assert_true(heap.remove_at(b) == Some(2))
assert_true(heap.pop() == Some(1))
}PairingHeap::contains
PairingHeap::into_sorted_array
PairingHeap::merge
PairingHeap::remove_at
PairingHeap::update
RadixHeap
A monotone heap over UInt64 keys: the key of a pushed entry may not be
smaller than the key of the last one popped. Under that rule a pop costs
O(log C) where C is the width of the key space, and it never compares two
keys of different buckets — the bucket a key falls in already says which is
smaller. That is what makes it a step faster than a comparison heap on
integer keys, and why a key below the last pop is refused rather than
reordered.
test {
let heap : @heap.RadixHeap[String] = @heap.RadixHeap::new()
heap.push(5UL, "five")
heap.push(1UL, "one")
heap.push(9UL, "nine")
assert_true(heap.pop_min() == Some((1UL, "one")))
assert_true(heap.pop_min() == Some((5UL, "five")))
}Install
Download zipData structures and algorithms the MoonBit core library leaves out.
data-structuresalgorithmscollectionscontainersstlmoonbitindex-mapindex-setmultimapbimapcounterflat-mapsorted-maprange-maptrieradix-treelru-cachelfu-cachearc-cacheexpiring-cachememoizesortingselectionbisectbinary-searchpermutationscombinationspowersetpartitionmergering-bufferslotmapgap-bufferbit-vectorbit-setlinked-listbinary-heapfibonacci-heappairing-heapmin-max-heapradix-heapdisjoint-setunion-findsegment-treefenwick-treeinterval-treeskip-listtreapbloom-filtercuckoo-filtercount-min-sketchhyperloglogtheta-sketcht-digeststring-searchsuffix-arraysuffix-automatondiffropeperfect-hash
Apache-2.0
Updated 9 hours ago
102 downloads