Notes :Binomial Heap [Draft]
Notes :Binomial Heap [Draft]
- A binomialheapis made up of a list of binomialtrees
- The main application ofBinary Heapis as implement priority queue Binomial Heap is an extension ofBinary Heapthat provides faster union or merge operation together with other operations provided by Binary Heap
- A binomial tree of order 0 is a single node
- A binomial tree of orderkhas a root node whose children are roots of binomial trees of ordersk−1,k−2, …, 2, 1, 0 (in this order)
- A binomial tree of orderkhas 2^k nodes, heightk
Order 3 has 8 nodes since 2³=8
Binomial tree of orderkcan be constructed from two trees of orderk−1 trivially by attaching one of them as the leftmost child of the root of the other tree
- If we have a heap with 13 items, we can express this in binary as 1101. This would translate to a binary tree of degree 3, a tree of degree 2, and a tree of degree 0 (with 2³ + 2² + 2⁰ = 8 + 4 + 1 items respectively = 13 total items)
- A Binomial Tree of Order n and depth r has nCr nodes (binomial coefficient )
A binomial heap is implemented as a set of binomial trees that satisfy thebinomial heap properties:
- Each binomial tree in a heap obeys theminimum-heap property: the key of a node is greater than or equal to the key of its parent.
(The first property ensures that the root of each binomial tree contains the smallest key in the tree, which applies to the entire heap.)
- There can only be eitheroneorzerobinomial trees for each order, including zero order. (eg number 13 is 1101 in binary)
// pending : Implementing Binomial Heap In Code
Merge Better
the advantage of a binomial heap is that it supportslog(n) merginggiven two binomial heaps.
binomial heap, you earn faster merging, but give up the O(1) find-min of a binary heap.
Links
The typical method of implementing the links between nodes is to have pointers to a parent, sibling and child. A tree does not have a direct link to all it’s immediate children, instead it goes to its first child and then iterates through each sibling. Here is an illustration of the regular pointer structure for a binomial tree.
Operations
Find minimum
Find minimum iterates through the roots of each binomial tree in the heap.
Insert
Insert creates a new heap with the inserted element which are then combined using the union operation.
Union
The union operation merges the two heaps together by continually linking trees of the same order until no two trees of the same order exist.
Extract minimum
Extract minimum iterates through the roots of each binomial tree in the heap to find the smallest node which is removed. The tree fragments are then reversed to form another heap
Decrease key
Decrease key reduces the specified node’s key and then bubbles it up through its ancestors until the tree meets the conditions of a heap
Delete
Delete is performed by calling decrease key to reducing the node to negative infinity which pulls the node to the top of the tree.
References
- https://www.growingwiththeweb.com/data-structures/binomial-heap/overview/
- https://www.geeksforgeeks.org/binomial-heap-2/