When merging 2 binary heaps (implemented as arrays), the worst case running time is O(n).
But I just want to figure out why its that.
So to do this, you would merge the two arrays in one, then create an empty heap, then for each element in the new array, you insert that element in the heap.
Now, to insert 1 element thats O(log(n)), but you do that n times, because once for each element. But then I'm getting O(n*log(n)). Why is this not right?
Yeah the optimal way is O(n), so I am trying to understand how the algorithm goes.
Suppose I have this array (the heap looks like in the picture). It currently is out of order and needs to be fixed. (into a max heap of type binary)
Can anyone help explain how this can be fixed?
A psuedocode algorithm is available here: Binary heap - Wikipedia, the free encyclopedia (Just below the "Delete" section)
EDIT:
Actually, here is an explanation of why the optimal method is O(n):
Binary heap - Wikipedia, the free encyclopedia
ok I understand how the algorithm works now and I see it's worst case running time is O(n), but how do you obtain whats the omega is? I believe it is supposed to be omega(n) which makes it theta(n), but how do you get omega(n)?