Member Avatar for lionsh

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?

  • 2 Contributors
  • 1 Reply
  • 87 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Rashakil Fol
Member Avatar for Rashakil Fol

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.