algorithm - 如何插入实现为二叉树的二叉最大堆？

Question

在实现为二叉树的二叉最大堆中（每个节点存储指向其父、左子和右子的指针），如果您有指向堆根的指针，您将如何实现插入操作？应该发生的是节点首先作为最后一行中的最后一个元素插入。对于基于数组，您可以追加到数组，但对于基于树的实现，您将如何找到正确的位置？

Answer 1

在这个较早的问题中，我给出了一个简短的算法，它使用数字k的二进制表示，以便找到一种方法来在自上而下的遍历中从二进制堆中选择第k个节点。假设您跟踪二进制堆的显式树表示中的节点数，您可以执行以下操作来执行插入操作：

1. 使用上面的算法，确定新节点应该去哪里，然后在那个位置插入节点。
2. 通过重新连接树以将其与其父级交换或通过交换节点及其父级的数据字段直到元素处于其最终位置，不断地向上冒泡节点。

希望这可以帮助！

Answer 2

如果您将新顶点挂在树的任何叶子下（作为左后继或右后继，无关紧要），然后从这个新顶点修复堆到顶部（也就是说，对于所有其他具有后继的顶点，交换它与更大的继任者并在需要时向上爬），您的新元素将在不破坏堆的情况下找到它的正确位置。但是，这只会保证您每个其他插入操作都将花费 O(h) 时间，其中 h 是树的最大高度。显然，最好将堆表示为一个数组，因为这样可以保证每个插入操作都将花费 O(logN) 时间。

Answer 3

为了找到应该插入新节点的确切位置，我们使用二进制堆大小的二进制表示。这需要 O(log N)，然后我们冒泡它需要 O(log N)。所以插入操作需要 O(log N) ......有关详细说明，请查看我关于二进制堆的博客文章 -

http://theoryofprogramming.com/2015/02/01/binary-heaps-and-heapsort-algorithm/

我希望它对你有帮助，如果有，请告诉我......！☺