平衡二叉搜索树和最大堆都可以在
如果我们从最大堆中删除最大值,则需要
在平衡二叉搜索树中,删除最大元素等于查找最大值+删除操作;它等于logn + logn,简化为
我读到了一种将最大堆应用于优先队列的方法,其主要目的是在每个出队操作中删除最大值。如果对于最大堆和平衡二叉搜索树,删除最大元素的时间复杂度均为
O(logn)
时间内执行插入和删除操作。但是,在最大堆中查找最大值的时间复杂度为O(1)
,而在平衡二叉搜索树中为O(logn)
。如果我们从最大堆中删除最大值,则需要
O(logn)
的时间复杂度,因为这是一个删除操作。在平衡二叉搜索树中,删除最大元素等于查找最大值+删除操作;它等于logn + logn,简化为
O(logn)
。因此,即使在平衡二叉搜索树中删除最大值也是O(logn)
。我读到了一种将最大堆应用于优先队列的方法,其主要目的是在每个出队操作中删除最大值。如果对于最大堆和平衡二叉搜索树,删除最大元素的时间复杂度均为
O(logn)
,那么我有以下问题:
为什么在优先队列中使用最大堆,而不是使用完全可搜索的平衡二叉搜索树?
由于没有平衡因子计算,最大堆可以称为非平衡二叉树吗?
每个平衡二叉搜索树都可以用作优先队列,并且也可以在
O(logn)
时间内进行搜索,但是最大堆的搜索时间复杂度为O(n)
,对吗?