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