如何将元素插入到以二叉树实现的二叉大根堆中？

Question

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

- omega

---

这个链表的形状是什么？如果父节点不能必然指向它们的子节点，那么节点以什么样的顺序链接？ - templatetypedef

链表将会长成这样：http://en.wikipedia.org/wiki/Binary_heap 因此，每个节点都将有一个指向其父节点、左子节点、右子节点和键值的指针。如果它是根节点或没有子节点，则为空。 - omega

是的，但是双向链表不是同一件事吗？因为你有指针两个方向（从父节点到子节点和从子节点到父节点）。 - omega

@omega- 它们具有相同的表示形式，但双向链表与一般树结构非常不同。双向链表是树的特殊情况，每个节点指向其子节点和父节点，因此将树表示描述为链表是不正确的。 - templatetypedef

@omega- 不可以。双向链表明确意味着您可以从第一个节点开始，然后连续向前迭代所有节点。树结构没有此属性 - 如果您持续跟随一个链接，您将无法到达树中的所有节点。 - templatetypedef

Answer 1

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

1. 使用上述算法确定新节点应该放置的位置，然后将节点插入该位置。
2. 通过重连树以与其父节点交换或交换节点及其父节点的数据字段，不断将节点向上冒泡，直到元素到达最终位置。

希望这可以帮助你！

- templatetypedef

---

那么如果您不知道堆的大小，就无法使用它了吗？ - omega

@omega- 没错。话虽如此，跟踪堆的大小非常容易，并且这样做对性能有巨大的好处。如果您不跟踪堆的大小，则插入的复杂度将为O(n)，因为您可能必须查看树中的每个节点才能确定插入点在哪里。如果您跟踪大小，则可以将其降至O(log n)，这是一个巨大的性能优势。 - templatetypedef

假设您不知道大小，插入的算法将是什么，以获得O(n)？ - omega

@omega- 你可以在树上执行 BFS，从左到右对节点进行排序。你访问的最后一个节点将是插入点（如果最后一行没有满），或者位于行末，因为你需要一个新行。基于此，您可以找到正确的插入点。或者，您可以只计算 O(n) 时间中的节点数，然后使用我的原始技术。 :-) 说真的，不存储节点计数是毫无意义的 - 它比替代方案简单得多，而且没有理由不这样做。 - templatetypedef

所描述的算法在log（n）中添加了一个节点，“end”，并且加上另一个O（log（n））用于冒泡。插入路径和冒泡路径相同。因此，您可以通过一次向下遍历该路径（不再需要父节点指针）来插入节点。 算法：使用描述的位算法转到路径上的下一个节点；将此路径节点与插入节点进行比较；如果它比插入节点大，则将插入节点放置在路径节点的位置，并设置插入节点=路径节点；继续使用（新的）插入节点，直到到达路径的末尾并在那里添加插入节点。完成！ - Bartel

Answer 2

如果您将新顶点挂在树的任何叶子下面（作为左或右后继，无论哪种方式），然后从此新顶点到顶部修复堆（即，对于具有后继的每个其他顶点，与更大的后继交换并在需要时向上爬升），您的新元素将找到其合适的位置而不会破坏堆。但是，这只能保证每次插入操作都需要O(h)时间，其中h是树的最大高度。 显然，将堆表示为数组更好，因为这样可以保证每次插入操作都需要O(logN)时间。

- K. Bulatov

---

这是正确的，但我正在尝试将其作为树实现。 - omega

如果您试图使树成为一个完全二叉树（通常情况下是这样的），那么这种设置将无法工作，因为您将不知道要插入哪个叶子节点。 - templatetypedef

正如我在这个答案中指出的那样，选择哪个叶子节点并不重要。只要在插入每个新顶点后进行反向修复，您的堆就会保持一致。但它不会是最优的。 - K. Bulatov

如果你想让它最优化，你可以将新元素插入到最靠近根节点的叶子下面。然后，插入操作将始终需要O(logN)时间，因为树将会自我调整。 - K. Bulatov

Answer 3

为了找到新节点应该插入的确切位置，我们使用二叉堆大小的二进制表示。这需要O(log N)，然后我们将其上移需要O(log N)。因此插入操作需要O(log N)...有关详细说明，请查看我博客上有关二叉堆的帖子 -

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

希望这对你有所帮助，如果有的话，请告诉我...！☺

- Vamsi Sangam