如何实现deleteMax()在MinHeap采取的log(n)时间 [英] How to implement deleteMax() in MinHeap taking log(n) time

查看:449
本文介绍了如何实现deleteMax()在MinHeap采取的log(n)时间的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我实施 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.

这篇关于如何实现deleteMax()在MinHeap采取的log(n)时间的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆