Prove that the number of comparisons between elements in binary heap build is at most (2N-2)

Question

I tried to think about this problem all day, and I'm having difficulties to get the answer. I would appreciate your help.

---

Suppose you have an array H with n elements.
Prove that the number of comparisons between elements in binary heap build is at most (2n-2).

---

pseudo code:

BUILD-MAX-HEAP (A)
1 heap-size [A] < - length[A]
2 for i <- Length[A]/2| downto 1
3 do MAX-HEAPIFY (A, i)

MAX-HEAPIFY (A, i)
1 l <- LEFT (i)
2 r <- RIGHT (i)
3 if l <= heap-size [A] and A[l] > Ali]
4    then largest <- l
5    else largest <- i
6 if r <= heap-size [A] and A[r] > A[largest]
7    then largest <- r
8 if largest ‡ i
9    then exchange A[i] with A[largest]
10   MAX-HEAPIFY (A, largest)

---

There is already a post about that question here, but I don't understand parts of the answer.

---

My thoughts

• BUILD-MAX-HEAP (A) is calling MAX-HEAPIFY (A, i) each iteration.

• On each iteration MAX-HEAPIFY (A, i) can be called again.

• Each time MAX-HEAPIFY (A, i) is called, there can be up to 2 comparisons.

• On 'leaves' we don't compare elements since there is no left child or right child (the iteration of BUILD-MAX-HEAP (A) don’t even bother to start with leaves).

• We cant tell if the last level is full of leaves but it doesn’t matter anyway.

• For each node (not the leaves) there are up to 2 comparisons and if MAX-HEAPIFY (A, i) is called again there are more 2 comparisons until we get to the lowest level (we go left/right depending which key is bigger).

I'm having difficulties to rephrase what I just said formally and get to the point where the number is 2n-2, so I would love to get your help :)