Computer Science

Computer Science RSS

Build-Heap number of comparisons

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.

•

Join Date: Apr 2006

Posts: 2

Reputation: lionsh is an unknown quantity at this point

Solved Threads: 0

lionsh

Offline

Newbie Poster

Build-Heap number of comparisons

Apr 19th, 2006

I need to prove that for binary heaps, BuildHeap does at most 2N-2
comparisons between elements.

I tried many approaches but i'm stuck.
I know that Build-Heap calls Heapify N/2 times.
each Heapify call you get 2 comparisons. the element with it's two sons.
then you have a recursive call to haepify.

can anyone help me with that?

•

Join Date: Jun 2005

Posts: 2,052

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: Build-Heap number of comparisons

Apr 20th, 2006

Prove it for the cases where N is one less than a power of two.

Then, as you add new elements across the new bottom row, find a pattern into how much each individual element contributes to the total possible number of comparisons.

All my posts may be redistributed under the GNU Free Documentation License.