HEAP-INCREASE-KEY复杂度

Question

让A成为一个堆，它不是以常规方式存储值，而只是定期存储根，并且每个子存储为它与其父项之间的差异。 HEAP-INCREASE-KEY（A，i，key）操作的复杂性是什么（操作更新节点上的节点的key到key）？

Answer 1

它可以在O(log N)时间像在一个正常的堆中完成。要找到存储在节点i中的新值，可以遍历从堆根目录到此节点的路径，以便根据它与其父节点之间的差异表示新的key值。之后，筛选程序可以以与在普通堆中完成的方式几乎相同的方式执行。在进行筛选程序交换时，这些值只会改变这两个交换节点及其子元素。因此，一次交换需要更新O(1)。这就是为什么总时间复杂度为O(log N)。

这是实现它的一种简单方法：
1.如果节点位于堆根和更新节点之间的路径上，我们称它为“已触及”节点。如果节点与最接近的“已触摸”节点之间的距离至多为2，我们称节点为“重建”。
2.对于每个“重建”节点，可以通过遍历堆来计算其真值。请注意，对于任何查询，都有O(log N)“重建”节点。
3.重建所有“重建”节点的真值后，可以运行一个通常的筛选程序。
4.在此过程完成后，可以通过遍历所有“重建”节点的堆来计算节点与其父节点之间的差异。所有其他节点都不会被触摸。