使用最少的更改将树转换为堆

Question

给定一棵k-ary树，我希望将其转换为具有最少更改次数的最小堆。更改被定义为重新标记节点。

我发现的一种解决方案是，我可以尝试更改节点值或不更改节点的dp解决方案。但是它在时间复杂度上会是指数级的？任何想法，(最好有最优性证明)。

例如:假设树是1-3，3-2，1-4，4-5。其中1是根。然后我可以将节点3重新标记为1或2，也就是说，在1个更改中，它变成了一个最小堆。

Answer 1

如果您要做的只是确保树满足heap属性(存储在每个节点中的键小于或等于存储在节点的子节点中的键)，那么您应该能够使用类似build-heap算法的东西，该算法以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。你把8换成7，你就得到了这棵树，它满足你的条件：

                    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堆。