README
¶
Package binomial
Tree Structure
Each box below is a Tree struct. Each Tree's child pointer is its first child in a linked list of direct children. The subsequent child in the list is the current child's sibling. Each child has a pointer back to its parent.
The rank, k, of each node is the rank of the tree below that node if you consider that node a root.
This entire diagram represents a rank 2 or degree 2 binomial tree. The Node pointers on each Tree are omitted for simplicity.
+---------+
+----->k: 2 |
| +---------+
| |parent |
| |sibling |
| +--+child |
| | +---------+
| |
| | +---------+ +---------+
| +-->k: 0 | +------>k: 1 <--+
| +---------+ | +---------+ |
+-----+parent | | +----+parent | |
| |sibling +-+ | |sibling | |
| |child | | +--+child | |
| +---------+ | | +---------+ |
| | | |
+-------------------+ | |
| +---------+ |
+-->k: 0 | |
+---------+ |
|parent +--+
|sibling |
|child |
+---------+
Heap Structure
A Heap contains a standard library doubly linked list where the Value for each list Element is a pointer to a Tree.
Documentation
¶
Overview ¶
Package binomial contains binomial tree and heap data structures.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap struct {
// contains filtered or unexported fields
}
Heap is a binomial heap.
func NewHeap ¶
NewHeap creates a new Heap with the given function to determine the lesser of two items on the heap. The Less function must handle each item added with Add.
type Less ¶
type Less func(a, b interface{}) bool
Less is a function that returns true if a is less than b.
Source Files