Build-Heap number of comparisons

Expand Post »

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?

Similar Threads

huffman code in C++
Heap block at 003D2CA0 modified at 003D2CB3 past requested size of b in C++
Heap of 8 with 8 comparisons in Computer Science
Algorithm Efficiency Help!!!! in C
Program alone doesn't help. in C++

lionsh

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Apr 2006

Permalink

Apr 20th, 2006

Re: Build-Heap number of comparisons

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.

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 173

Super Senior Demiposter

Offline

2,480 posts
since Jun 2005

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Computer Science Forum Timeline: Heap of 8 with 8 comparisons

Next Thread in Computer Science Forum Timeline: help plase

DaniWeb Message

Cancel Changes

User Name
Password