从最小堆切换到最大堆而不重新排列内部数组
假设我们有一个最小堆，其中一些元素满足堆属性。 如果我将算法从最小堆更改为最大堆而不重新排列内部数组，会发生什么情况？
也就是说，如果我保持数组不变，那么当我向内部数组追加一个元素时会发生什么？
Suppose we have a min heap with some elements which satisfy the heap property.
What happens if I change the algorithm from min heap to max heap without rearrange the internal array?
That is, if I keep the array unchanged, what happens when I append an element to the internal array?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
考虑以下来自 Wikipedia 的示例：
其数组表示如下所示：
现在我们将堆从最小“更改”为最大，但无需重新排列元素并插入新元素“25”。数组位置为 9，因此父节点在位置 4 处为“19”。
插入后，我们必须重复将新项与其父项进行比较，以确保堆属性（现在 max-heap =>parent 必须大于 child）。因此我们必须将“25”与“19”、“2”和“1”交换，直到它成为根节点。
现在最大堆属性适用于根节点（它的子节点确实更小），但不适用于其他节点，例如“3”仍然是“7”的父节点并且违反了最大堆条件。
总结一下：执行您所描述的操作不会将最小堆更改为最大堆。
Consider the following example from Wikipedia:
The array representation of this would look like this:
Now we "change" the heap from min to max, but without rearranging the elements and insert a new element "25". The array position would be 9 so the parent node is "19" at position 4.
After inserting we must repeatedly compare the new item with its parent to ensure heap property (now max-heap => parent must be greater than child). Thus we must swap "25" with "19", "2" and "1" until it is the root node.
Now the max-heap property holds for the root node (its children are indeed smaller), but not for the other nodes, e.g. "3" is still the parent of "7" and violates the max-heap condition.
To conclude this: Doing what you describe does not change the min-heap to a max-heap.
你只会把堆搞砸。
你必须重新堆化（这可以在 O(N) 时间内完成）。
You would just screw the heap.
You have to re-heapify (this can be done in time O(N)).