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

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

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

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

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

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

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