algorithm - 在不重新排列内部数组的情况下从最小堆切换到最大堆

Question

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

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

Answer 1

考虑以下来自 Wikipedia 的示例:

它的数组表示形式如下所示:

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

现在我们将堆从最小值“更改”为最大值，但不重新排列元素并插入新元素“25”。数组位置为 9，因此父节点在位置 4 处为“19”。

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

现在 max-heap 属性适用于根节点(它的子节点确实更小)，但不适用于其他节点，例如“3”仍然是“7”的父级并且违反了最大堆条件。

总而言之:执行您描述的操作不会将最小堆更改为最大堆。