algorithm - 如何在 MinHeap 中以 log(n) 时间实现 deleteMax()

Question

我正在实施MinHeap我知道如何实施deleteMax()但需要O(n)时间但我需要O(log(n))算法..

我搜索并没有找到一种方法来做到这一点，如果它存在我有什么办法可以deleteMax()吗O(log(n))？

Answer 1

您可以创建一个Min-max heap，它会deleteMin()在deleteMax()O(log n) 时间内完成。

这是我知道做你想做的事情的唯一 O(log n) 方式。Min-max heap 与 Min-heap 或 Max-heap 具有相同的渐近界，但它在现实世界中的运行时间会稍长一些。