Updated March 14, 2023
Introduction to Binomial Heap
Binomial Heap is another data structure like arrays, stacks, queues, linklists, and trees. It is a collection of binomial trees that satisfy the following properties:
- First, no two binomial trees in the collection have the same size.
- Second, each node in the collection has a key.
- Each binomial tree in the collection satisfies the heap properties.
- Finally, tFourth, the roots of the binomial trees are connected and are in increasing order.
A binomial tree of order k is defined as follows:
- In a binomial tree, there are exactly
- is a pair of trees, where the root of one becomes the leftmost child of the other (for all ).
- Two ’s are combined to get one, the having a minimum value at the root will be the root of, the other will become the child node.
Representing Binomial Heap In Memory
- Each node x in a heap have the following fields:
- key[x]: contains data
- p[x]: pointer to x’s parent
- child[x]: pointer to the leftmost child of x
- sibling[x]: pointer to the sibling of x immediately to its right
- degree[x]: containing a number of children
- If x has no children child[x] = NIL.
- If x has the rightmost child of its parent, then sibling[x] = NIL.
- If x is a root p[x] = NIL.
- If x is a root, then sibling [x] points to the next root in the list.
- If x is the last root in the root list sibling[x] = NIL.
- A given heap H is accessed by the field head[H], which is simply a pointer to the first root list of H.
- If binomial heap H has no elements, the head[H] = NIL.
Implementation of Binomial Heap
key[x]: contains data
p[x]: pointer to x’s parent
child[x]: pointer to the leftmost child of x
sibling[x]: pointer to the sibling of x immediately to its right
degree[x]: containing several children
class Node{
int key;
Node p;
Node child;
Node sibling;
int degree;
}
Operations On Binomial Heaps
Below are the different operations on binomial heaps:
Creating A Binomial Heap
- To make an empty binomial heap: the MAKE_BINOMIAL_HEAP procedure simply allocates and returns an object H, where head[H] = NIL.
- Since it takes equally constant time so the running time will be.
Finding The Minimum Key
- The procedure BINOMIAL_HEAP_MINIMUM returns a pointer to the node with the minimum key in an n-node binomial heap H.
- Since binomial heap is min-heap-ordered, the minimum key must reside in a root node.
- The procedure finds the minimum element from the root list.
- This implementation assumes that there are no keys with value.
- The running time of BINOMIAL-HEAP_MINIMUM is O(logn) since there are at the most floor(logn) +1 roots to check.
- When called on a heap of figure BINOMIAL_HEAP_MINIMUM return address of node containing 1.
Syntax For BINOMIAL_HEAP_MINIMUM(H)
yNIL
xhead[H]
min
while x NIL
do if key[x] < min
then min key[x]
y x
xsibling[x]
return y
Binomial Link Procedure
- The procedure BINOMIAL_LINK(y, z)links the tree rooted at node y to the tree rooted at z.
- It makes z the parent of node y.
- Node z thus becomes the root of a
Syntax For BINOMIAL_LINK(y, z)
p[y]z
sibling[y]child[z]
child[z]y
degree[z]degree[z]+1
Uniting Two Binomial Heaps
- Given two binomial heaps H1, and H2 BINOMIAL_HEAP_UNION(H1, H2) creates a single binomial heap.
- First, we simply merge two heaps in increasing order of degrees.
- After that, we need to make sure there is at most one Binomial tree of any degree so that we combine binomial trees of the same degree.
- Traverse the list.
- While traversing the list of merged roots, we keep three-pointers prev-x, x, and next-x.
- While traversing the following 4 cases may occur
- Case 1: degree[x]degree[next-x]
- Simply march ahead of the list
- Case 2: degree[next-x]-degree[sibling[next-x]]
- Simply march ahead of the list
- The next iteration either executes Case 3 or Case 4
- Case 3 or Case 4: degree[x] = degree[next-x]degree[sibling[next-x]]
- Case 3: key[x]key[next-x]
- Remove next-x from root list and link to x.
- Case 4: key[x]>key[next-x]
- Remove x from root list and link to next-x
- Case 1: degree[x]degree[next-x]
Syntax For BINOMIAL_HEAP_UNION(H1, H2)
HMAKE_BINOMIAL_HEAP
head[H]BINOMIAL_HEAP_MERGE(H1, H2)
free the objects H1 and H2 but not the lists they point to
If head[H] = NIL
Then return H
prev-xNIL
xhead[H]
next-xsibling[x]
while next-xNIL
do if (degree[x]degree[next-x]) or
(sibling[next-x]NIL and degree[sibling[next-x]] = degree[x])
then prev-xx
xnext-x
else if key[x]key[next-x]
then sibling[x]sibling[next-x]
BINOMIAL_LINK(next-x, x)
else if prev-x = NIL
then head[x]next-x
else sibling[prev-x]next-x
BINOMIAL_LINK(x, next-x)
xnext-x
next-xsibling[x]
return H
Uniting Two Binomial Heaps – Analysis
- Let H1 contains n1 nodes and H2 contains n2 nodes, so that n = n1 +n2
- Then H1 contains at most floor(logn1)+1 roots and H2 contains at most floor(logn2)+1 roots
- So H contains at most floor(logn1)+floor(logn2) + 22 floor(log n) + 2 = O(logn)
- The time to perform BINOMIAL_HEAP_MERGE is thus O(logn) iterations.
- Thus BINOMIAL_HEAP_UNION(H1, H2) takes O(logn)
Inserting A Node
- The following procedure inserts node x into heap H, assuming that x has already been allocated and key[x] has been filled in.
- The procedure simply makes a one-node binomial heap H’ in O(1) time and unites it with a node binomial heap in O(logn) time.
Syntax For BINOMIAL_HEAP_INSERT(H, x)
H’<-MAKE_BINOMIAL_HEAP()
p[x]<-NIL
child[x]<-NIL
sibling[x]<-NIL
degree[x]<-NIL
degree[x]<-0
head[H’]<-x
H<-BINOMIAL_HEAP_UNION(H,H’)
Conclusion
In this article, we have covered most of the topics related to the binomial heap. After reading this article, we have concluded that binomial heap is a non-linear data structure and a collection of binomial trees that satisfies some special conditions. We can join two binomial heaps using union syntax. It works on dynamic memory allocations that mean it allocates memory to the data during run time.
Recommended Articles
This is a guide to Binomial heap. Here we discuss that binomial heap is a non-linear data structure and a collection of binomial trees that satisfy some special conditions. You may also have a look at the following articles to learn more –
