Heap is a popular data structure used in various forms like Min heap and max heap and is mostly used to reduce the time complexity of complex problems. But here we will be discussing a bit different kind of Heap, Binomial Heap.
Table of Contents
Binomial Heap
It is a collection of Binomial Trees. A Binomial tree Bk is a tree consisting of two Binomial trees Bk-1 which are linked together. The root of one is the leftmost child of the root of others.
Properties
- Every Binomial Tree (Bk) must have 2k nodes.
- The height of the Binomial tree is k.
- There are (k i) nodes in each level I where, i runs from 0 to k.
- the root has degree k, which is greater than that of any other node; moreover, if the children of the root are numbered from left to right by k − 1, k − 2…, 0, child i is the root of a subtree Bi.
Taking these properties into account, a Binomial Heap is a collection of such trees. This data structures also have some particular properties like-
- The key of a node is greater than or equal to the key of its parent.
- There is at most one tree in the binary heap whose root has a given degree.
- The number of Binomial Trees = number of set bits in the binary form of n, where n is the number of nodes of a Binary Heap.
Supported Methods
- Union (): This operation is used to merge two binomial heaps into one. Most of the heap operations use this method. Suppose we have two Binary Heaps H1, H2, we can call Union(H1, H2) to combine them into a single heap.
- Insert(): This method is used to insert nodes with (H, Key) to our Binomial Heap H. This method then calls the Union() to combine this node with the previous Heap.
- Min(): returns the minimum key in logn time.
- Max(): returns the maximum key in logn time.
- Delete(): removes a key from the heap.
- DecreaseKey(): assigns to node x within heap H the new key-value k, which is assumed to be no greater than its current key value.
Let us see the algorithm for some of these functions separately:
- Union (H1, H2): It basically links the roots of two Binomial Heaps with root H1 and H2, if these are linked either of them can be the new root of the Binomial Tree. Its algorithm can be represented as:
sibling[H1]=child[H2]
child[H2]=H1
degree[H2]++;
H = HEAP()
root[H] = BINOMIAL-HEAP-MERGE(H1, H2)
free the objects H1 and H2 but not the lists they point to
if root[H] = NIL
then return H
prev-x = NIL 7 x = head[H]
next-x = sibling[x]
while next-x = NIL
do if (degree[x] = degree[next-x]) or (sibling[next-x] = NIL and degree[sibling[next-x]] = degree[x])
then prev-x = x and 2 12 x = next-x and
if key[x] ≤ key[next-x] 14 then sibling[x] = sibling[next-x]
BINOMIAL-LINK(next-x, x)
else if prev-x = NIL
then root[H] = next-x
else sibling[prev-x] = next-x
BINOMIAL-LINK(x, next-x)
x = next-x
next-x = sibling[x]
return H
Insert(): Is used to insert keys into the heap.
p[x] = NIL
child[x] = NIL
sibling[x] = NIL
degree[x] = 0
head[H ] = x
H = UNION(H, H )
Min(): Is used to get the minimum from the heap
find the root x with the minimum key in the root list of H, and remove x from the root list of H
reverse the order of the linked list of x’s children, and set root[H] to point to the head of the resulting list
H = UNION(H, H )
return x
Well, now when we are done with the basic algorithm, lets dig deep in the implementation of it.
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
// node data structure
struct Node {
int data; // contains the key
int degree; // number of children
Node *p; // pointer to parent
Node *child; // pointer to the leftmost child
Node *sibling; // pointer to the right sibling
};
typedef Node *Ptr;
// Class that represents Binomial heap data structure
class BinomialHeap {
private:
// head points to the root of the leftmost binomial tree
Ptr root;
// initializes the node with default values
// all pointers are initialized to nullptr
void initializeNode(Ptr node, int data, int deg) {
node->data = data;
node->deg = deg;
node->p = nullptr;
node->child = nullptr;
node->sibling = nullptr;
}
// merge two binomial trees of same deg
static void BINOMIAL_LINK(Ptr x, Ptr y) {
// x must be parent of y
y->p = x;
y->sibling = x->child;
x->child = y;
// increase the deg of x
x->deg += 1;
}
public:
BinomialHeap() {
root = nullptr;
}
// find the node with mininum data
Ptr min() {
// traverse all the roots and find compare
int min = 999999; //store a max
Ptr currPtr = root;
Ptr minPtr = nullptr;
while (currPtr != nullptr) {
if (currPtr->data < min) {
min = currPtr->data;
minPtr = currPtr;
}
currPtr = currPtr->sibling;
}
return minPtr;
}
// create sample heap (given in figure 5) with three trees for testing
void createSampleHeap1() {
// B0
Ptr node1 = new Node;
initializeNode(node1, 5, 0);
root = node1;
// B1
Ptr node2 = new Node;
initializeNode(node2, 17, 1);
Ptr node3 = new Node;
initializeNode(node3, 27, 0);
node2->child = node3;
node3->p = node2;
// link B0 and B1
node1->sibling = node2;
// B3
Ptr node4 = new Node;
initializeNode(node4, 12, 3);
Ptr node5 = new Node;
initializeNode(node5, 18, 2);
Ptr node6 = new Node;
initializeNode(node6, 16, 1);
Ptr node7 = new Node;
initializeNode(node7, 15, 0);
Ptr node8 = new Node;
initializeNode(node8, 23, 1);
Ptr node9 = new Node;
initializeNode(node9, 30, 0);
Ptr node10 = new Node;
initializeNode(node10, 22, 0);
Ptr node11 = new Node;
initializeNode(node11, 25, 0);
node4->child = node5;
node5->p = node4;
node6->p = node4;
node7->p = node4;
node5->child = node8;
node5->sibling = node6;
node6->child = node10;
node6->sibling = node7;
node8->p = node5;
node9->p = node5;
node10->p = node6;
node8->child = node11;
node8->sibling = node9;
node11->p = node8;
// link B1 and B3
node2->sibling = node4;
}
// create sample heap (given in figure Fig 10 (a))
void createSampleHeap2() {
// B0
Ptr node1 = new Node;
initializeNode(node1, 5, 0);
root = node1;
// B2
Ptr node2 = new Node;
initializeNode(node2, 6, 2);
Ptr node3 = new Node;
initializeNode(node3, 12, 1);
Ptr node4 = new Node;
initializeNode(node4, 34, 0);
Ptr node5 = new Node;
initializeNode(node5, 33, 0);
node2->child = node3;
node3->p = node2;
node4->p = node2;
node3->child = node5;
node3->sibling = node4;
node5->p = node3;
// link B0 and B1
node1->sibling = node2;
// B3
Ptr node6 = new Node;
initializeNode(node6, 1, 3);
Ptr node7 = new Node;
initializeNode(node7, 2, 2);
Ptr node8 = new Node;
initializeNode(node8, 12, 1);
Ptr node9 = new Node;
initializeNode(node9, 6, 0);
Ptr node10 = new Node;
initializeNode(node10, 4, 1);
Ptr node11 = new Node;
initializeNode(node11, 13, 0);
Ptr node12 = new Node;
initializeNode(node12, 18, 0);
Ptr node13 = new Node;
initializeNode(node13, 7, 0);
node6->child = node7;
node7->p = node6;
node8->p = node6;
node7->p = node6;
node7->child = node10;
node7->sibling = node8;
node8->child = node12;
node8->sibling = node9;
node10->p = node7;
node11->p = node7;
node12->p = node8;
node10->child = node13;
node10->sibling = node11;
node13->p = node10;
// link B1 and B3
node2->sibling = node6;
}
// create sample heap
void createSampleHeap3() {
// B1
Ptr node1 = new Node;
initializeNode(node1, 29, 1);
Ptr node2 = new Node;
initializeNode(node2, 33, 0);
node1->child = node2;
node2->p = node1;
root = node1;
// B2
Ptr node3 = new Node;
initializeNode(node3, 21, 2);
Ptr node4 = new Node;
initializeNode(node4, 23, 1);
Ptr node5 = new Node;
initializeNode(node5, 78, 0);
Ptr node6 = new Node;
initializeNode(node6, 50, 0);
node3->child = node4;
node4->p = node3;
node5->p = node3;
node4->child = node6;
node4->sibling = node5;
node6->p = node4;
// link B1 and B2
node1->sibling = node3;
}
// insert a node to the heap
void insert(int data) {
BinomialHeap h;
Ptr node = new Node;
initializeNode(node, data, 0);
h.setRoot(node);
merge(h);
}
// returns the root pointer
Ptr getRoot() {
return root;
}
// setter for root
void setRoot(Ptr root) {
this->root = root;
}
// merge two binomial heaps H and H'
// resulting heap will be H
void merge(BinomialHeap h1) {
Ptr curr1 = getRoot();
Ptr curr2 = h1.getRoot();
Ptr curr3 = nullptr;
Ptr temp = nullptr;
if (curr1->deg <= curr2->deg) {
curr3 = curr1;
curr1 = curr1->sibling;
} else {
curr3 = curr2;
curr2 = curr2->sibling;
}
temp = curr3;
// merge two heaps without taking care of trees with same deg
// the roots of the tree must be in accending order of deg from
// left to right
while(curr1 != nullptr && curr2 != nullptr) {
if (curr1->deg <= curr2->deg) {
curr3->sibling = curr1;
curr1 = curr1->sibling;
} else {
curr3->sibling = curr2;
curr2 = curr2->sibling;
}
curr3 = curr3->sibling;
}
if (curr1 != nullptr) {
// copy all the remaining trees of heap1
while(curr1 != nullptr) {
curr3->sibling = curr1;
curr1 = curr1->sibling;
curr3 = curr3->sibling;
}
}
if (curr2 != nullptr) {
// copy all the remaining trees of heap2
while(curr2 != nullptr) {
curr3->sibling = curr2;
curr2 = curr2->sibling;
curr3 = curr3->sibling;
}
}
// scan the merged list and repeatidly merge binomial trees with same deg
curr3 = temp;
Ptr prev = nullptr;
Ptr next = curr3->sibling;
while (next != nullptr) {
// if two adjacent tree roots have different deg or 3 consecutive roots have same deg
// move to the next tree
if ((curr3->deg != next->deg )|| (next->sibling != nullptr && curr3->deg == next->sibling->deg)) {
prev = curr3;
curr3 = next;
} else {
// otherwise repeatdly merge binomial trees with same deg
if (curr3->data <= next->data) {
curr3->sibling = next->sibling;
BinomialHeap::BINOMIAL_LINK(curr3, next);
} else {
if (prev == nullptr) {
temp = next;
} else {
prev->sibling = next;
}
BinomialHeap::BINOMIAL_LINK(next, curr3);
curr3 = next;
}
}
next = curr3->sibling;
}
setRoot(temp);
}
// deletes the smallest node from the heap
Ptr deleteMin() {
Ptr curr = root;
Ptr prevMin = nullptr;
// find the root with minimum key
Ptr minPtr = nullptr;
Ptr prevPtr = nullptr;
int min = 999999;
while (curr != nullptr) {
if (curr->data <= min) {
min = curr->data;
prevMin = prevPtr;
minPtr = curr;
}
prevPtr = curr;
curr = curr->sibling;
}
// delete the node pointed by minPtr
if (prevMin != nullptr && minPtr->sibling != nullptr) {
prevMin->sibling = minPtr->sibling;
} else if (prevMin != nullptr && minPtr->sibling == nullptr) {
prevMin->sibling = nullptr;
}else if(prevMin == nullptr and minPtr->sibling != nullptr) {
root = minPtr->sibling;
}else if(prevMin == nullptr and minPtr->sibling == nullptr) {
root = nullptr;
}
// remove parent reference from all its child
Ptr childPtr = minPtr->child;
while (childPtr != nullptr) {
childPtr->p = nullptr;
childPtr = childPtr->sibling;
}
// reverse the order
stack<Ptr> s;
childPtr = minPtr->child;
while (childPtr != nullptr) {
s.push(childPtr);
childPtr = childPtr->sibling;
}
curr = s.top();
Ptr temp = curr;
s.pop();
while (!s.empty()) {
curr->sibling = s.top();
s.pop();
curr = curr->sibling;
}
curr->sibling = nullptr;
BinomialHeap h;
h.setRoot(temp);
// merge
merge(h);
// return the min root
return minPtr;
}
};
int main() {
BinomialHeap heap1;
BinomialHeap heap2;
BinomialHeap heap3;
heap1.createSampleHeap2();
heap2.createSampleHeap3();
heap1.merge(heap2);
heap1.printHeap();
heap1.deleteMin();
heap1.printHeap();
return 0;
}
Time Complexities
Operations | Binomial Heap |
Union | O(logn) |
Insert | O(logn) |
Min | O(logn) |
DeleteMin | O(logn) |
Frequently Asked Questions
Union operation in Binary heap takes linear time whereas Binomial Heap takes logarithmic time. Hence, we have more merging operations we prefer Binomial Heap.
Well, there can be multiple uses in multi-threading but I could find a really interesting application of this in Rubik’s cube solving algorithm.
Hope this article has cleared a lot of doubts about Binomial Heap and also as an introduction to this data structure. It might help programmers and developers. Keep following Coding Ninjas for more such interesting blogs.
By Aniruddha Guin
Leave a Reply