binomial heap.pptx for advanced data structure

bfhdfhfdh

1. Binomial Heap

2. Binomial Heap The binary heap data structure is fine for the simple operations of inserting, deleting and extracting elements, but other operations aren't so well supported. One such operation is the Union operation, which joins two heaps together. If the heaps are binary heaps then this requires building up a new heap from scratch, using the elements of the old heaps, which is expensive for large heaps. Binomial heap presents the data structure, which supports Union operations more efficiently.

3. Binomial Trees The binomial tree is the building block for the binomial heap. A binomial tree is an ordered tree that is, a tree where the children of each node are ordered. Binomial trees are defined recursively, building up from single nodes. A single tree of degree k is constructed from two trees of degree k - 1 by making the root of one tree the leftmost child of the root of the other tree.

4. The Binomial Heap Properties A binomial heap is a collection of binomial trees that satisfies the following binomial-heap properties: No two binomial trees in the collection have the same size. Each node in each tree has a key. Each binomial tree in the collection is heap- ordered in the sense that each non-root has a key strictly less than the key of its parent. The number of trees in a binomial heap is O(log n).

5. Implementation of a Binomial Heap A field key for its key A field degree for the number of children A pointer child , which points to the leftmost-child A pointer sibling, which points to the right-sibling A pointer p , which points to the parent

6. The roots of the trees are connected so that the sizes of the connected trees are in decreasing order. Also, for a heap H, head [H] points to the head of the list

7. Operations on Binomial Heaps Creation of a new heap. Search for the minimum key. Uniting two binomial heaps. Insertion of a node. Removal of the root of a tree. Decreasing a key. Removal of a node.

8. Search for the Minimum Key To do this we find the smallest key among those stored at the roots connected to the head of H. What's the cost of minimum-search? The cost is O(log n) because there are O(log n) heaps, in each tree the minimum is located at the root, and the roots are linked.

9. Find Minimum Key

10. Insert New Node

11. Delete a Node

12. Unite Two Binomial Heaps

13. Binomial Heap Union Create heap H that is union of heaps H’ and H”. “Mergeable heaps” Easy if H’ and H” are each order k binomial trees Connect roots of H’ and H” Choose smaller key to be root of H Running Time O(log N)