修改当前最小值和其他一些元素后重新堆化数组（最小）堆

Question

我有一个类似于问题1和问题2的问题。 Q-1 描述了一种修改数组单个元素并重新排序的方法。 Q-2 讨论从堆中删除一个元素，然后通过替换根堆中的最后一个元素并将其向下冒泡来重新堆化。

在Q-2的方法中，从堆中删除元素是否会产生内存重新排列成本？如：在每次外部迭代中，我必须从头开始重新分配堆，而不是使用现有的堆。将当前最小值设置为

+Inf

并将其向下冒泡而不是更改堆大小，以便我可以在

A

的迭代中重用相同的内存占用量，会有好处吗？

我问这个问题是因为我有一个应用程序，其中外部例程

A

调用内部例程

B

，它通过（i）将当前最小值设置为

v

，并且（ ii) 使用最小值（在设置为

+Inf

之前）来确定其他一些要修改的元素。所以我更愿意维护一个初始大小的堆数组

+Inf

，但有效地排除一些索引/人为/懒惰地修改堆的大小，而不是动态地这样做。两个问题：

我避免动态内存变化的逻辑有意义吗？我所描述的内容有实现吗？

1. 如果我知道我想修改未排序值列表中的一些索引
n
2. （除了当前的

   [1,5,10]

   之外），我如何将其转换为我的堆数组的索引？

Answer 1

例如，增加堆的常见方法是加倍。也就是说，您最初分配一个数组来容纳 16 个项目。您可以通过保留

argmin

变量来跟踪使用了多少个。每当你添加到堆中时，你就会增加

Count

。每当你删除某些东西时，你就会减少

Count

。当堆必须增长到超过 16 个项目时，您需要重新分配，使大小变为 32。您并没有消除重新分配的开销，但大大减少了它。如果您预先知道堆将包含 20,000 个项目，那么您可以使用该大小初始化支持数组，并且根本不需要重新分配。要

更改

堆中的某个项目（即修改其值），您可以就地进行更改，然后根据需要将其向上冒泡或向下筛选。无需删除或插入任何内容。 要从堆中

删除

一个项目，请将要删除的项目替换为堆上的最后一个项目，然后根据需要向上冒泡或向下筛选。 https://stackoverflow.com/a/8706363/56778 提供了更多相关信息。