使用最大堆和平衡二叉搜索树实现优先队列的区别

Question

3

平衡二叉搜索树和最大堆都可以在O(logn)时间内执行插入和删除操作。但是，在最大堆中查找最大值的时间复杂度为O(1)，而在平衡二叉搜索树中为O(logn)。

如果我们从最大堆中删除最大值，则需要O(logn)的时间复杂度，因为这是一个删除操作。

在平衡二叉搜索树中，删除最大元素等于查找最大值+删除操作；它等于logn + logn，简化为O(logn)。因此，即使在平衡二叉搜索树中删除最大值也是O(logn)。

我读到了一种将最大堆应用于优先队列的方法，其主要目的是在每个出队操作中删除最大值。如果对于最大堆和平衡二叉搜索树，删除最大元素的时间复杂度均为O(logn)，那么我有以下问题：

所有时间复杂度均计算于最坏情况。如有任何疑问，请随时咨询。

- user3205479

2个回答

2

优先队列中使用最大堆的目的是什么，仅仅因为它易于实现而不使用完全可搜索的平衡二叉搜索树？一些最大堆的优点包括：

如果初始输入是一个数组，则该数组可以作为堆使用，这意味着不需要额外的存储空间。虽然可以想出一些方法在原地使用数组创建BST，但对于原始类型来说，这将是相当奇怪的，并会增加更多的处理开销。BST通常是从头开始创建的，将数据复制到节点中。

有趣的事实是：有序数组也是一个堆，因此如果已知输入是有序的，则无需进行任何操作即可构建堆。

堆可以作为数组存储而不需要存储交叉引用，而BST通常由具有左右引用的节点组成。这至少有两个后果：

- BST所使用的内存大约是堆的3倍。 - 尽管堆和BST的几个操作具有相同的时间复杂度，但调整BST的开销要大得多，因此在BST情况下，实际花费在这些操作上的时间是一个（常数）因子更大。

由于没有平衡因子的计算，最大堆可以称为不平衡二叉树吗？实际上，堆是完全二叉树，因此它总是尽可能平衡：叶子节点始终位于最后或倒数第二层。自平衡 BST（如 AVL、红黑树等）无法超越这种高度的平衡，其中往往会出现三个或更多级别的叶子节点。

每个平衡的 BST 都可以用作优先队列，并且在 O(logn) 的时间内可进行搜索，但是最大堆的搜索时间是 O(n)，这是正确的吗？是的，这是正确的。因此，如果应用程序需要搜索功能，则 BST 优于最大堆。

- trincot

很好的完整回答，但是你可以在O(n)时间内构建一棵BST。我还想补充一点，一个最大堆只需要10分钟就能写出来，而支持删除操作的自平衡BST则需要数小时的编写和单元测试。 - Matt Timmermans

@MattTimmermans，如果你能在O(n)时间内构建一棵二叉搜索树，那么你也可以在O(n)时间内进行排序。我认为这是不可能的，除非你需要类似于基数排序之类的额外假设。你能澄清一下吗？ - trincot

OIC，我开始使用的是排序数组，但你开始使用的是未排序数组，在堆方面效果很好。我的错误。 - Matt Timmermans

如果输入数组已经排序，则堆也具有优势：在这种情况下，输入已经表示为堆，因此不需要采取任何操作来构建它。 - trincot

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zazaeil · Accepted Answer

优先队列中为什么要使用最大堆，而不是使用完全可搜索的平衡二叉树呢？这只是因为最大堆易于实现吗？

不是这样的。最大堆更适合，因为它被精心设计为尽快（在O(1)时间内）返回下一个（符合优先级的）元素。这正是你想要从最简单的优先队列中得到的。

由于没有平衡因子计算，最大堆可以称为不平衡的二叉树吗？

不是这样的。也有一种平衡方法。长话短说，通过上移或下移操作（交换顺序不正确的元素）来平衡堆。

每个平衡的二叉搜索树都可以用作优先队列，并且在O(logn)时间内进行搜索，但是最大堆搜索是O(n)，对吗？

是的！同样，链表和数组也可以使用。只是在O-记号方面更昂贵，在实践中速度更慢。