question on binary heaps

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?

Quote:

---

Originally Posted by Sneaky

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 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?

---

I'm curious, why do you say insertion of n elements has a running time of O(log(n)) ?

I mean, inserting 1 element is O(log(n)), so for inserting n elements, shouldn't it be O(n*log(n))?

Quote:

---

Originally Posted by Sneaky

I mean, inserting 1 element is O(log(n)), so for inserting n elements, shouldn't it be O(n*log(n))?

---

Bear with me please, I'm also trying to wrap my head around this problem.

Wouldn't you need to find the largest/smallest elements in the heap when merging or creating a new heap? That has a running time of O(n).

Wikipedia says that inserting elements one by one indeed takes time O(n*log(n)) and is not the optimal way to create a heap. But "heapifying" any array of length n takes time O(n).

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?

http://i.imgur.com/1vtEl60.png

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