# question on binary heaps

• Jan 23rd 2013, 05:13 PM
Sneaky
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?
• Jan 23rd 2013, 07:54 PM
janvdl
Re: question on binary heaps
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)) ?
• Jan 23rd 2013, 07:56 PM
Sneaky
Re: question on binary heaps
I mean, inserting 1 element is O(log(n)), so for inserting n elements, shouldn't it be O(n*log(n))?
• Jan 24th 2013, 06:09 AM
janvdl
Re: question on binary heaps
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).
• Jan 24th 2013, 12:37 PM
emakarov
Re: question on binary heaps
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).
• Jan 24th 2013, 03:43 PM
Sneaky
Re: question on binary heaps
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
• Jan 24th 2013, 09:06 PM
janvdl
Re: question on binary heaps
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
• Jan 25th 2013, 05:30 PM
Sneaky
Re: question on binary heaps
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)?