algorithm - 词入二叉堆

Question

用以下文字展示最小二叉堆的形成。它们按以下顺序插入:There, will, be, Consequences, jim。

我知道大写字母的单词被认为比其他以非大写字母开头的单词小。如果只有一个大写字母的话，我知道我们可以在上面表示它。但是，我们如何显示一个堆，其中有两个大写字母的单词。

为什么大写字母被认为比非大写字母小？

谢谢

Answer 1

首先让我们考虑如何对单词进行排序:

Consequences < There < be < jim < will

所以我们可以给他们编号，这样更容易使用:

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

首先我们添加There == 2 :

                                       2

然后 will == 5和 be == 3 :

                                       2
                                      / \
                                     5   3

到目前为止一切顺利。但是现在添加 Consequences == 1 时我们必须堆化:

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

最后我们添加 jim == 4 :

                                         1
                                        / \
                                       2   3
                                      / \
                                     5   4

至于比较字母，是因为ASCII编码。所以字母如下:

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