二叉堆 - 插入顺序

Question

插入顺序会影响二叉堆的结构吗？我的意思是，当以不同的顺序插入相同的元素时，是否有可能得到一些不同的父子关系， 例如：

20 6 3 5 7 8 16 10 (inserting order #1) and 6 3 20 10 16 3 7 5 (inserting order #2)

或者最终结果应该总是一样的？

Answer 1

如果您想象序列 1 1 1 1 2 2 和 1 1 2 1 1 2，您应该会得到不同的堆。

    1              versus          1
 1     1                        1     2
1 2   2                        1 1   2

Answer 2

堆可以以不同的方式存储给定的值集合。例如，如果堆恰好是一棵完美的二叉树，那么您可以在不违反堆的情况下将任何子树与其兄弟子树交换 属性.

例如，如果数据集合的值为 1、2 和 3，则有 2 个可能的堆可以表示该数据集：

         1                   1
        / \                 / \
       2   3               3   2

第一堆就是插入2before3时的结果，第二堆就是插入2after时的结果] 3.

如果我们查看具有四个值（例如 1、2、3 和 4）的输入，我们可以将其表示为四个堆：

          1            1           1           1
         / \          / \         / \         / \
        2   3        2   4       3   2       4   2
       /            /           /           /
      4            3           4           3

同样，插入的顺序将决定最终结果是这四个堆中的哪一个。