我实施 MinHeap 我知道如何实现 deleteMax（），但它需要 O（N）时间 但我需要 O（日志（N））算法..

I'm implementing MinHeap I know how to implement deleteMax() but it takes O(n) time But I need O(log(n)) algorithm..

我搜查，并没有找到一个方法来做到这一点，如果它存在 有什么办法，我可以 deleteMax（）在 O（日志（N））次？

I searched and didn't find a way to do this, if it exists Is there any way that I can deleteMax() in O(log(n)) times?

推荐答案

您可以创建一个 MIN-最大堆，这确实 deleteMin（）和 deleteMax（）在O（log n）的时间。

You could create a Min-max heap, which does deleteMin() and deleteMax() in O(log n) time.

这是唯一的O（log n）的方法，我知道这样做你想要的。最小 - 最大堆具有相同的渐近边界为最小堆还是最大堆，但其运行时间真实世界会稍微长一些。

That's the only O(log n) way I know of to do what you want. The Min-max heap has the same asymptotic bounds as a Min-heap or Max-heap, but its real world running time will be somewhat longer.