algorithm - 使用最少的更改次数将树转换为堆

Question

给定一个 k-ary 树，我想将其转换为一个最小堆，并且更改次数最少。更改被定义为重新标记节点。

我发现的一个解决方案是，我可以尝试更改节点值或不更改的 dp 解决方案。但它的时间复杂度会呈指数级增长吗？任何想法，（最好有最优性证明）。

示例：假设树是 1-3、3-2、1-4、4-5。其中 1 是根。然后我可以将节点 3 重新标记为 1 或 2，即在 1 中更改它成为一个最小堆。

Answer 1

如果您要做的只是确保树满足堆属性（存储在每个节点中的键小于或等于存储在节点子节点中的键），那么您应该能够使用类似build-堆算法，它在 O(n) 中运行。

考虑这棵树：

                    8
              -------------
             |      |      |
            15      6      19
           /  \     |    / |  \
          7    3    5   12 9  22

现在，从下往上，将每个节点尽可能地向下推到树上。也就是说，如果节点大于其任何子节点，则将其替换为其最小的子节点，并在必要时这样做直到达到叶级别。

例如，您查看值为 15 的节点。它比其最小的子节点大，因此您交换它，生成子树：

           3
         /   \
        7     15

此外，6 个位置与 5 交换，19 个位置与 9 交换位置，为您提供此树：

                    8
              -------------
             |      |      |
             3      5      9 
            / \     |    / |  \
           7  15    6   12 19  22

请注意，在叶级别的下一个节点，每个节点都小于其最小的子节点。

现在，根。由于规则是将节点与其最小的子节点交换，因此将 8 与 3 交换，给出：

                    3
              -------------
             |      |      |
             8      5      9 
            / \     |    / |  \
           7  15    6   12 19  22

但是你还没有完成，因为 8 大于 7。你用 7 交换 8，你得到了这棵树，它符合你的条件：

                    3
              -------------
             |      |      |
             7      5      9 
            / \     |    / |  \
           8  15    6   12 19  22

如果树是平衡的，则整个过程的复杂度为 O(n)。如果树严重不平衡，则复杂度为 O(n^2)。有一种方法可以保证 O(n)，不管树的初始顺序如何，但它需要改变树的形状。

我不会声称该算法保证任何给定树的“最小更改次数”。然而，我可以证明，对于平衡树，算法是 O(n)。请参阅https://stackoverflow.com/a/9755805/56778，其中解释了二进制堆。该解释也适用于 d-ary 堆。