How many comparisons does 8 element Binary Heap need?

Question

This is a homework question, and I'm asked to show that 8 element Binary Heap needs 8 comparisons.

but when I use an example such: 1 2 3 4 5 6 7 8 I'm not sure if I should go bottom up or top down. but anyways, I've tried them both.

In top down: I've done it in 8 steps but when I count the number of comparisons I get 13 :S

In bottum up: I've done it in 7 steps but when I count the number of comparisons I get 10 :S

After Trying the algorithm here is the comparisons I got:

1. H[L]=8 > H[i]=4
2. H[L]=8 > H[i]=2, H[r]=5 > H[Largest]=8
3. H[L]=4 > H[i]=2
4. H[L]=6 > H[i]=3, H[r]=7 > H[Largest]=6
5. H[L]=8 > H[i]=1, H[r]=7 < H[Largest]=8
6. H[L]=4 > H[i]=1, H[r]=5 > H[Largest]=4

hmmm, any help on how should I count the number of comparisons so I can show them 8? and what method shall I use(bottom up or top down)?

Answer 1

I believe the accepted answer is incorrect.

Building a heap bottom-up is in fact O(n), but this is only an upper bound that applies to the general case. It is possible to perform better than that on specific cases, such as when we have 8 elements. I'll present below at least one way in which a heap of 8 elements can be built in 8 comparisons.

Let's say we have 8 elements {A, B, C, D, E, F, G, H}, and we know nothing about their relative ordering. We begin by making comparisons between any four pairs of the eight elements. After this step, we have done 4 comparisons and now have 4 ”ordered” pairs, as exemplified below:

A > B, C > D, E > F, G > H

Now, notice that with 1 comparison we can put two pairs together in a tree of N = 4. For example, if we take the first two pairs and compare A and C, we end up with either the tree on the left below (if A > C) or the one on the right (if C > A):

    A     |       C 
  C   B   |     A   D
D         |   B

We apply the same process to the other two pairs, ending up with two trees of N = 4 using 6 comparisons so far. We have something like:

    A              E 
  C   B   and    G   F
D              H

With one extra comparison, we can decide which one has higher ordering between A or E. Let's say A > E without loss of generality. We have used 7 comparisons so far. Finally, we use our last comparison left to decide the ordering between the elements below A (B and C) and use that information to rearrange the tree on the left above to one of the two below (B > C on the left, C > B on the right):

 A        |   A     
   B      |     C   
 C   D    |   B   D

Finally, since we already know that A > E, it is easy to now join the two trees we have (the one rooted in E and the one rooted in A), as shown below:

         A
    E         B
  G   F     D   C
H

And we're done, we have a heap of 8 elements built with 8 comparisons. Hopefully everything was understandable hahaha