Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinomialHeap ¶
A max binomial heap.
It has higher constant for insert and pop, but supports merging in O(log(len)).
func (*BinomialHeap[T]) Len ¶
func (b *BinomialHeap[T]) Len() int
Return the number of element.
time complexity: O(1)
space complexity: O(1)
Example ¶
heap := BinomialHeap[int]{Cmp: func(a, b int) int { return a - b }} fmt.Println(heap.Len()) heap.Push(123) fmt.Println(heap.Len())
Output: 0 1
func (*BinomialHeap[T]) Merge ¶
func (b *BinomialHeap[T]) Merge(heap BinomialHeap[T])
Merge and destruct the heap into the current heap.
time complexity: amortized O(log(len1) + log(len2))
space complexity: O(1)
Example ¶
// Merge two binomial heaps and print the top element after merging heap1 := BinomialHeap[int]{Cmp: func(a, b int) int { return a - b }} heap1.Push(5) heap1.Push(3) heap2 := BinomialHeap[int]{Cmp: func(a, b int) int { return a - b }} heap2.Push(10) heap2.Push(8) heap1.Merge(heap2) fmt.Println(heap1.Len()) fmt.Println(heap1.Top())
Output: 4 10
func (*BinomialHeap[T]) Pop ¶
func (b *BinomialHeap[T]) Pop()
Remove the top element from the heap.
time complexity: O(log(len))
space complexity: O(1)
Example ¶
heap := BinomialHeap[int]{Cmp: func(a, b int) int { return a - b }} heap.Push(5) heap.Push(3) heap.Push(7) fmt.Println(heap.Top()) heap.Pop() fmt.Println(heap.Top())
Output: 7 5
func (*BinomialHeap[T]) Push ¶
func (b *BinomialHeap[T]) Push(e T)
Push e to the heap.
time complexity: amortized O(log(len))
space complexity: O(1)
Example ¶
heap := BinomialHeap[int]{Cmp: func(a, b int) int { return a - b }} heap.Push(5) heap.Push(3) heap.Push(7) fmt.Println(heap.Len()) heap.Push(10) fmt.Println(heap.Len()) fmt.Println(heap.Top())
Output: 3 4 10
func (*BinomialHeap[T]) Top ¶
func (b *BinomialHeap[T]) Top() T
Return the top of the heap.
time complexity: O(1)
space complexity: O(1)
Example ¶
heap := BinomialHeap[int]{Cmp: func(a, b int) int { return a - b }} heap.Push(5) heap.Push(3) heap.Push(7) fmt.Println(heap.Top())
Output: 7
Click to show internal directories.
Click to hide internal directories.