从最小堆切换到最大堆而不重新排列内部阵列

Question

假设我们有一个min heap,其中包含一些满足heap属性的元素.如果我将算法从最小堆更改为最大堆而不重新排列内部数组会发生什么？

也就是说,如果我保持数组不变,当我将一个元素附加到内部数组时会发生什么？

Answer 1

考虑维基百科的以下示例:

这个的数组表示如下所示:

[1, 2, 3, 17, 19, 36, 7, 25, 100]

现在我们将堆从"min"更改为"max",但不重新排列元素并插入新元素"25".数组位置为9,因此父节点在位置4处为"19".

插入后,我们必须反复比较新项目与其父项,以确保堆属性(现在max-heap => parent必须大于child).因此,我们必须将"25"与"19","2"和"1"交换,直到它成为根节点.

现在max-heap属性适用于根节点(其子节点确实较小),但不适用于其他节点,例如"3"仍然是"7"的父节点并且违反了最大堆条件.

总结一下:执行您描述的操作不会将最小堆更改为最大堆.

Answer 2

你只需拧紧堆.

您必须重新堆积(这可以在时间O(N)中完成).