CODEWITHSUNDEEP
algorithmmergeheapbig-obinomial-heap
OneRaynyDay
OneRaynyDay

Reputation: 3968

Why is the merge function of binomial heaps O(logN) rather than O(logN * logN)?

For those who know this very well, just read the bolded text below for the actual question.

Preface of auxilliary functions:

I know that merging two binomial trees of the same rank is O(1) since all that's necessary is to append the head of T1 as the child of the other. I also know that inserting a tree that is of order equal to or less than the least order tree in the binomial heap is O(logN), since the "carry-over" effect of merging applies. Imagine a binomial heap of T_0,T_1,T_2,...,T_n(where subscript is the order), and we add a new T' of order 0. This would lead to a carry-over n times of merging trees of the same order. We know n = log(N).

The merge function itself:

In the merge function, the two heaps are added to a new heap tree by tree, in a mergesort kind of way. We add the lowest order tree of either heap into the new heap, and if both orders are the same, then we merge(O(1)) it and insert(O(logN)) it to the resulting tree after it has been built recursively. Since we will insert trees of lowest order first, the merge will always be inserting a tree of equal or less than order than the first tree in the new heap.

Where the confusion happens:

I'm confused as to why the merge function is O(logN), instead of O(logN*logN). We know that each insert is O(logN), and we have logN trees, where N = N1+N2 where N1 and N2 are # of elements in each starting heap. If we have two heaps in the structure where it leads to the situation where the carryover effect of inserting will happen every single insert into the new heap, wouldn't it be O(logN * logN)?

Perhaps I'm missing some key understanding here. Any help is appreciated! Extra thanks if you tell me where in my understanding I went wrong :)

Upvotes: 3

Views: 1434

Answers (2)

arunkumaraqm
arunkumaraqm

Reputation: 367

Let us merge two Binomial Heaps, one of rank n and another of rank m where m is not more than n. Every binomial heap can be represented as a binary number. Eg: 1010 is a binomial heap with a degree-3 binomial tree and a degree-1 binomial tree. Here is some Python code for the merge function:

    def merge(heap_one, heap_two):
        # heap_one has n nodes and heap_two has m nodes
        # A BinomialHeap object consists of an array of BinomialTrees called trees
        # where each element of the array is a BinomialTree or is None
        for tree in heap_two.trees:
            if tree != None:
                heap_one.add_tree(tree)

Suppose heap_one is 1111 and heap_two is 111. These two heaps are respectively the worst-case heaps for their rank. By that I mean, 1111 is worse than 1011 or 1101 or 1000. The number of nodes in heap_one is 1+2+4+8 = 15. The rank of heap_one is 4 = log(15 + 1). The number of nodes in heap_two is 1+2+4 = 7. The rank of heap_two is 3 = log(7 + 1). We're using log with base 2 here.

For merging, going by the code, we first do 1111 + 1, then (1111 + 1) + 10 and then ((1111 + 1) + 10) + 100. 1111 + 1 = 10000 -- that's 4 carries generated. 10000 + 10 = 10010 -- 0 carries generated. 10010 + 100 = 10110 -- 0 carries generated. The total no. of carries generated is 4 in this example. You cannot have an example where the no. of carries generated is more than log n.
To merge 1001 and 101, 1 carry is generated. To merge 1111 and 1111, 4 carries are generated. To merge 11111 and 1111, 5 carries are generated.

Let's go back to merging 1111 and 111. The four carries were generated in the first iteration of the loop, making heap_one 10000. That's an O(logn) operation. When 0 carries are generated, it's an O(1) operation. Informally, logn + (logm - 1) * 1 = logn + logm - 1 < 2logn - 1 < 2logn O(logn) + (O(logm) - 1) = O(logn + logm) = O(logn) since m <= n. Note: logm - 1 is the no. of nodes in heap_two that don't generate a carry.

Let's merge 1011 and 111. 1011 is not the worst-case rank 4 binomial heap. 1011 + 1 = 1100 -- 2 carries generated. 1100 + 10 = 1110 -- 0 carries generated. 1110 + 100 = 10110 -- 2 carries generated. The first 2 carries were generated from the 0th and 1st bits of 1011. The next 2 carries were generated from the 2nd and 3rd bits. So, merge is an O(logn) operation.

Upvotes: 1

misztsu
misztsu

Reputation: 129

You probably don't understand the algorithm. When we have two trees of same order, we don't "merge (O (1)) it and insert (O (log N))". You think that when we get such "merged" tree we leave it and at the end, we insert it node by node, right? Then to make it O (logN): When you have two trees of order k, you merge them and get one tree of order k+1. Now, depending on how many k+1 order trees you have from heaps you are merging, you have one, two or tree k+1 order trees:

if 1 this tree is just a part of the merged heap

if 2 you merge these two and do this point again on k+2 order trees

if 3 one is part of merged heap, and you merge other 2 into k+2 order tree

All of these are O(1) so when you do it at log(n) + 1 orders you get O(log(n)) heap merge.

Upvotes: 2

Related Questions