我知道最小配对堆可以比 O(logn) 更快地减少密钥。但是，有没有办法让增加键的操作也比减少键的置顶、删除、插入新操作更快，时间复杂度为O(logn)？好像没有参考文献谈到过这个。
我通常会看到 increase-key 和 decrease-key 在堆讨论中被视为同一件事。
在配对最小堆中，decrease-key 的摊销运行时复杂度为 O(log n)。有时操作非常快，有时也非常昂贵，但总体来说是 O(log n)。 increase-key也有 O(1) 的情况，以及比 O(log n) 更昂贵的情况。
您可以优化increase-key。毕竟，如果您增加密钥，那么它不会小于根。事实上，它不会比它自己的父级小。因此，您可以删除它，增加键，然后将其插入到原来的位置，而不是删除键并插入到顶部。
我不清楚这能为您节省多少（如果有的话）。这实际上取决于节点的子列表中有多少个子节点。以及配对堆的运行时行为。事实证明，这样的优化可能会减少 increase-key 的时间，但会改变堆的行为，例如 remove-min 会更昂贵。配对堆的行为有时很难预测。
无论如何，尽管您可以进行一些优化来减少特定情况下的运行时间，但不太可能降低 O(log n) 的平均情况复杂度。