c++ - 需要有关简单左派堆插入结果的帮助

Question

我有一个（最小）左派堆，如下所示：

               1
            /     \
            8      6
          /   \   /  \
         10   12 14   16
                 /\   /
               18 20  22

我被要求显示插入 21 的结果。我对左派堆的理解是，插入只是单个节点的合并，在这种情况下，应该将 21 与每个右父节点进行比较，直到它到达 16 的 NULL 子节点，并且应该自动放置在那里。我错了吗？它应该去别的地方吗？

Answer 1

我不知道为什么评论者如此关心节点排序。也许他们甚至不知道左派堆是什么？

原来答案是它确实变成了 16 的右孩子，但是因为 6 的 NPL 变成了 2，这大于左树的 1 的 NPL，所以你必须交换 8 和 6 树的位置。