Words into a binary heap

Question

Show the formation of a min binary heap with the following words. They are inserted in the following order: There, will, be, Consequences, jim.

I know that the words with capital letters are considered to be smaller than the other words starting with non-capital letters. If there is only one word with a capital letter then, i know that we can represent it on top. However, how do we show a heap where there are two words with capital letters.

And why does capital letters are considered to be smaller than non-capital letters?

Thank you

Answer 1

First let's consider how the words are to be sorted:

Consequences < There < be < jim < will

so we can give them numbers so it's easier to work with:

1 = Consequences
2 = There
3 = be
4 = jim
5 = will

First we add There == 2:

                                       2

then will == 5 and be == 3:

                                       2
                                      / \
                                     5   3

so far so good. But now when adding Consequences == 1 we have to heapify:

                          2                 1
                        /   \              / \
                       5     3     ==>    2   3
                      /                  /
                     1                  5

And finally we add jim == 4:

                                         1
                                        / \
                                       2   3
                                      / \
                                     5   4

As to comparing letters, it's because ASCII coding. So the letters go as follows:

A < B < C < .. < Z < a < b < c < ... < z

Answer 2

I am assuming you mean building the heap iteratively and heapifying after each insertion if needed. We simply need to start adding the words:

First, you simply add There:

  There

Then, you add 'will'

      There
will

Similarly for 'be'

      There
will        be

Now, you add Consequences:

                   There
            will         be
Consequences

But Consequences < will so you need to sift up:

                     There
       Consequences         be
will

And again, because Consequences < There

                Consequences  
       There                  be
will

Now, we can add 'jim':

                Consequences  
       There                  be
will        jim

And since There<jim - we are done!

Answer 3

Capital letters are lexicographically smaller when referring to the ASCII-Table (http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange), perhaps you meant that.

Answer 4

You'd build a min-heap the way you would with numbers, but instead of numerical comparison, you'll be doing lexicographic comparisons.

Comparing 2 words lexicographically/alphabetically works like this: compare the first letter, if equal, compare the next one, etc.

Capital letters are considered "smaller" because they have a lower character code value. That is, they are lexicographically smaller, because they come "before" the small-case letters. If you look at an ASCII table:

You see that A has the ASCII value of 65, whereas a has the value of 97. Unicode has the same character codes for these letters, so the same is true there.