EDUCBA

EDUCBA

MENUMENU
  • Explore
    • Lifetime Membership
    • All in One Bundles
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Binomial heap

Binomial heap

Updated March 14, 2023

Binomial heap

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:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

  • 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

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 –

  1. Heap Data Structure
  2. Heap Sort in C
  3. What is Heap Memory?
  4. Seaborn heatmap
ADVERTISEMENT
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

🚀 Extended Cyber Monday Price Drop! All in One Universal Bundle (3700+ Courses) @ 🎁 90% OFF - Ends in ENROLL NOW