最小堆中增加键的边界是什么

Question

我在测试中被问到这个问题，想确保我回答正确：

You are given a min heap. We want to increase all the nodes on the left most path (so the root, node 2, node 4, node 8......) by a value of c, so that the heap stays a min heap.

What is the limitation on c?

例如，最小堆可以是：

                   ___2___
                  /       \
               __8__       7
              /     \     / \
             9      10  11   13
            / \    /
          15  12  14

最左边的路径由值 2、8、9 和 15 组成

预期的答案是：c = 2

Answer 1

节点值的增加可能不会导致该值变得大于其 children 值之一的情况。这对左边 child 来说从来都不是问题，因为它的值增加了相同的数量，但它会成为右边 child 的问题，因为该值不会改变。

在最左边路径的节点中（除了最后一个，它没有右child），你必须找到它们右child之间的最小差异]的价值，以及自己的价值。那将是c可以得到的最大值。

在示例堆中，这些差异是（从顶部开始）：

7-2 = 5
10-8 = 2
12-9 = 3

这些差异中的最小值是 2。所以对于这个例子，答案是 2。

最小堆中增加键的边界是什么

What are the boundaries on increasing keys in minimum heap

heap

min-heap