将字母插入空堆

Question

我正在尝试将 "KONTINUASJONSEKSAMEN" 插入到空堆中。结果应该会产生 "USTSOSNOMNJNNEKAAKEI"，但我做不到。我最终得到 "UTSSOONSMNJNNEKAAKEI"，这是我从下面的可视化中计算出来的。

                                 U
                             /        \  
                            T           S 
                         /    \       /   \    
                       S       O     O     N
                     /  \     / \   / \   / \ 
                    S    M    N  J  N  N E   K
                   / \   /\   /
                  A  A   K E I

我从顶部的第一个 K 开始，向下，从左到右处理单词的其余部分，在较低值 parents 和较高值 children 之间切换。其中较高的值意味着更接近 Z。

你知道我错在哪里了吗？

Answer 1

我认为问题在于您是自上而下进行插入，而该堆是通过自下而上进行插入而构建的。我使用了自己的堆实现来执行自下而上的插入，并且从该输入字符串产生的堆正是您预期的输出。

如果你是在二叉堆中做自上而下的插入，那么遇到这种情况就会产生歧义：

    K
  S   S
 A B C D

也就是说，您要插入的节点小于它的两个子节点，并且两个子节点相等。

你选择和哪个 'S' 交换？如果你总是选择左边的那个，而其他人总是选择右边的那个，那么最终的堆可能会大不相同。例如：

    S           S
  K   S       S   K
 A B C D     A B C D

两者都是有效的堆。

通常，堆插入是通过将新节点添加为堆的最后一个节点，然后将其冒泡到树中的适当位置来完成的。因此，如果您从根部的 K 开始并添加 O，则您有：

  K
 O

你注意到 O 大于 K，所以你交换节点得到：

  O
 K

然后你加上N得到

  O
 K N

你先把 T 添加为堆的最后一个节点，然后冒泡起来：

   O
 K   N
T

T 大于 K，因此交换节点：

   O
 T   N
K

并且 T 大于 O，所以你交换它们：

   T
 O   N
K

这样自底向上插入，没有歧义

您还应注意，自下而上插入比自上而下插入更有效。如果在顶部插入，那么它 always 需要 log₂(n) 次迭代，其中 n 是堆中当前的项目数。即使新项替换了根，您也必须筛选直到在叶级有一个新条目。

当您通过首先将新节点放在叶级别来进行自底向上插入时，有一半的时间节点将留在叶级别。并且 75% 的时间节点不会上升超过一级。唯一需要进行 log₂(n) 交换的时间是新项替换根项时。有一个很好的论据可以证明二叉堆插入是 O(1)，但假设是自下而上的插入。有关详细信息，请参阅。

有关如何实现自下而上插入的更多信息，请参阅我在 http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/ 上关于堆的博客系列。

Answer 2

我找到了一个快速的方法。我没有用树叶打字和擦除无尽的树，而是将字符设置在一个数组中，为每个 1st、2nd、4th、8th、16...字符画一条线。求助热线左侧的字符是求助热线右侧相邻字符的 parent(s)。字符1是parent到2和3。字符2是parent到4和5等等。我再次测试左 child 是否大于 parent，如果是则它们切换（注意我的 workbook/excel 文档中的切换直接在前一个 parent/child 之下）。然后我检查了右边的 child 和（新的）parent。附上我的 excel 文档的屏幕截图。

将字母插入空堆

Inserting letters onto an empty heap

heap

insert