In computer science , a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged together. It is important as an implementation of the mergeable heap abstract data type also called meldable heap , which is a priority queue supporting merge operation. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. A binomial heap is implemented as a set of binomial trees compare with a binary heap , which has a shape of a single binary tree , which are defined recursively as follows: .
|Published (Last):||1 September 2004|
|PDF File Size:||1.76 Mb|
|ePub File Size:||4.28 Mb|
|Price:||Free* [*Free Regsitration Required]|
We think you have liked this presentation. If you wish to download it, please recommend it to your friends in any social system. Share buttons are a little bit lower. Thank you! Published by Hilary Alexander Modified about 1 year ago. Remove the minimum root and meld? Union : increase potential Extract-Min : decrease potential. This can pay for handling all the trees involved in the link.
Define the rank of Bk to be k. Items at the nodes, heap ordered. Parent pointers needed for delete. Basic operation is meld h1,h2 : Like addition of binary numbers. Findmin h : obvious Insert x,h : meld a new heap with a single B0 containing x, with h deletemin h : Chop off the minimal root. Meld the subtrees with h. Update minimum pointer if needed. Example: binary counter single operation -- increment On the worst case increment takes O k.
Meld h1,h2 : Concatenate the lists of binomial trees. Update the minimum pointer to be the smaller of the minimums O 1 worst case and amortized. Successive linking: Traverse the forest keep linking trees of the same rank, maintain a pointer to the minimum root. Once we encounter a second tree of some rank we link them and keep linking until we do not have two trees of the same rank. Meld h1,h2 , Insert x,h -- as before Delete x,h : simply mark x as deleted.
What is the amortized cost of find-min? How many new trees are created by the purging step? One of them has degree at least ki Therefore in its subtree there are at least 2 ki-1 nodes. Proof cont. Add the resulting tree to the end of the queue.
Denote it also by T Edges with one endpoint in T are stored in a heap data structure. Denoted by h T. We use binomial queues with lazy meld and deletion. Find e by doing find-min on h T. We never explicitly delete edges! We can determine whether an edge is deleted or not by two find operations. Then we can determine whether a node is marked deleted in O 1 time, and our analysis is still valid. So, we have at most 2m implicit delete operations that cost O m.
The complexity of these find-min operations dominates the complexity of the algorithm. Let pi be the number of deleted edges purged from the heap at the find-min performed by the i-th iteration.
We want to bound the sum of these expressions. Pass 1 is when we remove the original singleton trees from the queue. Pass i is when we remove trees added to the queue at pass i What is the size of a tree removed from the queue at pass j? At least 2j. Prove by induction So how many passes are there? At most log n. Some contexts where some things.
Theoretical curiosity and some applications. Similar presentations. Upload Log in. My presentations Profile Feedback Log out. Log in. Auth with social network: Registration Forgot your password?
Download presentation. Cancel Download. Presentation is loading. Please wait. Copy to clipboard. Union : increase potential Extract-Min : decrease potential 47 Extract-Min : Amortized Analysis Let Ti be the number of trees after the ith operation Let r be the rank of the tree containing the min. Define the rank of Bk to be k 67 Binomial heaps def A collection of binomial trees at most one of every rank. Example: binary counter single operation -- increment 72 Amortized analysis Cont.
Lazy binomial heap
Heaps Binomial Heaps Lazy Binomial Heaps 1.