3

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 :)

Community
  • 1
  • 1
OneRaynyDay
  • 3,658
  • 2
  • 23
  • 56

2 Answers2

2

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.

misztsu
  • 129
  • 5
  • Thank you for the answer! I wasn't thinking we'd insert it node by node, but rather that we'd insert the merged trees into the heap tree by tree. And I thought when we're inserting the trees one by one it would take logn time each resulting in logn*logn. Is the latter understanding correct? – OneRaynyDay Jun 27 '16 at 16:30
  • Yes, it is I think – misztsu Jun 27 '16 at 16:35
  • Then I think your answer might be lacking in that in case 2 you'd get a k+2 tree after merging again, but what if there was 2 k+2 trees after, then 2 k+3 trees and so on? That would mean logn number of trees would have to be merged everytime you add a new tree right? – OneRaynyDay Jun 27 '16 at 16:41
  • Yes, I don't actually understeand why did you call it lacking now, isn't logn merging what we wanted? – misztsu Jun 27 '16 at 16:58
  • But that's per tree? We have multiple trees to merge. – OneRaynyDay Jun 27 '16 at 17:03
  • No, that logn is there not for one tree, but for all trees of higher order. When we have 2 k+1 trees, 2 k+2, then 2 k+3 trees and so on, and we merge k order trees, then after applying algorithm through higher orders once, there will be one tree on each order, so no more tree to merge – misztsu Jun 27 '16 at 17:18
  • Oh I see, does that mean there's never a case when the merge operation would bubble up more than once? – OneRaynyDay Jun 27 '16 at 17:41
1

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.

arunkumaraqm
  • 337
  • 1
  • 13