使用最大堆和平衡BST实现优先级队列
平衡BST和最大堆都在O(logn)中执行插入和删除。但是，在最大堆中找到最大值是O(1)，但在平衡BST中这是O(logn)。
如果我们移除最大堆中的最大值，则采用O(logn)，因为它是delete操作。
在平衡BST中，删除max元素=查找max值+删除；它等于logn + logn，减为O(logn)。因此，即使删除平衡BST中的最大值也是O(logn)。
我已经读过一个这样的应用程序max堆是一个优先级队列，它的主要目的是为每个去队列操作删除最大值。如果删除max元素对于max堆和平衡BST都是O(logn)，则我有以下问题
- 优先级队列中的最大堆的目的是什么，因为它很容易实现，而不是使用完全可搜索、平衡的BST？
- 由于没有平衡因子计算，所以最大堆可以称为不平衡二叉树？
- 每个平衡的BST都可以用作优先级队列，在
O(logn)中也是可搜索的，但是最大堆搜索是正确的吗？
所有的时间复杂性都是为最坏的情况计算的。任何帮助都是非常感谢的。
回答 2
Stack Overflow用户
发布于 2021-01-25 13:05:27
优先级队列中的最大堆的目的是什么，因为它很容易实现，而不是使用完全可搜索、平衡的BST？
堆的一些优点是：
- 给定一个未排序的输入数组，一个时间，而一个时间。
- 如果初始输入是数组，则该数组可以用作堆，这意味着它不需要额外的内存。尽管人们可以想出使用数组中现有数据创建BST的方法，但这将是相当奇怪的(对于原始类型而言)，并且会带来更多的处理开销。BST通常是从头创建的，在创建数据时将数据复制到节点中。 有趣的事实:一个排序的数组也是一个堆，所以如果知道输入是排序的，就不需要做什么来构建堆。
- 堆可以作为数组存储，而不需要存储交叉引用，而BST通常由具有左右引用的节点组成。这至少有两个后果：
- The memory used for a BST is about 3 times greater than for a heap.
- Although several operations have the same time complexity for both heap and BST, the overhead for adapting a BST is much greater, so that the actual time spent on these operations is a (constant) factor greater in the BST case.由于没有平衡因子计算，所以最大堆可以称为不平衡二叉树？
堆实际上是一个完全二叉树，所以它总是尽可能平衡:叶子总是位于最后或最后一个级别。一种自平衡的BST (如AVL，红黑，.)无法超越高水平的平衡，在那里，你经常会有三个层次或更多的叶子发生。
每个平衡的BST都可以用作优先级队列，并且在O(logn)中也是可搜索的，但是最大堆搜索是对的吗？
是的，这是真的。因此，如果应用程序需要搜索功能，那么BST就更优越了。
Stack Overflow用户
发布于 2021-01-25 09:53:26
优先级队列中的最大堆的目的是什么，因为它很容易实现，而不是使用完全可搜索、平衡的BST？
不是的。Max堆更适合，因为在O(1)时间内，它被仔细地检测，以便尽快返回next (尊重优先级)元素。这就是您希望从最简单的优先级队列中得到的。
由于没有平衡因子计算，所以最大堆可以称为不平衡二叉树？
不是的。这也是一个平衡。长话短说，堆的平衡是通过移位或移位操作来完成的(交换不正常的元素)。
每个平衡的BST都可以用作优先级队列，并且在O(logn)中也是可搜索的，但是最大堆搜索是对的吗？
嗯!也可以使用链接列表或数组。它只是会更昂贵的O-表示法，在实践中要慢得多。
https://stackoverflow.com/questions/65882138
复制相似问题
腾讯云开发者
