2

优先队列：基本操作：插入删除（删除最小元素）

目标：为上述功能提供有效的运行时间或增长顺序。

优先队列的实现方式：

Linked List: Insertion will take o(n) in case of insertion at end o(1) in case of 
             insertion at head.
             Delet (Finding minumum and Delete this ) will take o(n) 

BST:
   Insertion/Deltion of minimum = In avg case it will take o(logn) worst case 0(n)

AVL Tree: 
   Insertion/deletion/searching: o(log n) in all cases.

我的困惑在这里：

为什么我们不使用 AVL 树来实现优先级队列，为什么我们选择二进制堆......虽然我们知道在 AVL 树中我们可以在最坏的情况下在 o(log n) 中进行插入/删除/搜索。

4

3 回答 3

3

二叉堆不是二叉搜索树（BST）。如果严重不平衡/恶化成一个列表，确实需要 O(n) 时间。堆通常总是 O(log(n)) 或更好。IIRC Sedgewick 声称基于数组的堆的平均时间为 O(1)。

为什么不是 AVL？因为它在结构中维护了太多的秩序。太多的秩序意味着，太多的努力去维持这个秩序。我们可以摆脱的订单越少越好 - 它通常会转化为更快的操作。例如，RBT 优于 AVL 树。RBT，红黑树，几乎是平衡树——它们节省了操作，同时仍然保证了 O(log(n)) 时间。

但是任何树都是完全有序的结构，所以堆通常更好，因为它们只确保最小元素在顶部。它们只是部分排序的。

于 2012-05-29T09:42:20.710 回答
3

复杂性并不是一切，实际性能还有其他考虑因素。

对于大多数目的，大多数人甚至不使用 AVL 树作为平衡树（就我所见，红黑树更常见），更不用说作为优先级队列了。

这并不是说 AVL 树没用，我很喜欢它们。但他们确实有一个相对昂贵的插件。AVL 树的好处（甚至击败红黑树）是在不修改的情况下进行大量查找。这不是优先级队列所需要的。

作为一个单独的考虑因素——不要介意你的 O(log n) 插入二进制堆，斐波那契堆有 O(1) 插入和 O(log N) 最小删除。有很多数据结构可供选择，权衡略有不同，因此您不会期望看到每个人都只选择满足您（非常简短）标准的第一个东西。

于 2012-05-29T09:39:14.857 回答
2

因为在二叉堆中，最小元素是根。

于 2012-05-29T09:39:02.890 回答