为什么我们通过堆而不是二进制搜索树进行排序？

Question

可以在O(n logn)时间内从列表构造堆,因为将元素插入堆需要O(logn)时间并且有n个元素.

类似地,可以在O(n logn)时间内从列表构造二叉搜索树,因为将元素插入到BST中需要平均登录时间并且存在n个元素.

从最小到最大遍历堆需要O(n logn)时间(因为我们必须弹出n个元素,并且每个pop需要O(logn)接收器操作).从最小到最大遍历BST需要O(n)时间(字面上只是顺序遍历).

所以,在我看来,构造两个结构需要相同的时间,但BST迭代的速度更快.那么,为什么我们使用"Heapsort"代替"BSTsort"呢？

编辑:感谢Tobias和lrlreon的回答!总之,以下是我们使用堆而不是BST进行排序的要点.

• 堆的构造实际上可以在O(n)时间内完成,而不是O(nlogn)时间.这使堆构造比BST构造更快.
• 此外,数组可以很容易地就地转换为堆,因为堆总是完整的二叉树.BST不能轻易实现为数组,因为BST不能保证是完整的二叉树.这意味着BST需要额外的O(n)空间分配来进行排序,而Heaps只需要O(1).
• 堆上的所有操作都保证为O(logn)时间.除非平衡,否则BST可能具有O(n)运算.堆积比平衡BST更容易实施.
• 如果您需要在创建堆后修改值,则只需应用接收器或游泳操作即可.修改BST中的值在概念上更加困难.

Answer 1

我可以想象有多种原因，您希望在搜索树上更喜欢（二进制）堆：

• 结构：二进制堆实际上可以在O（n）的时间通过应用构建heapify操作自下而上从最小到最大的子树。

• 修改：二叉堆的所有操作都比较简单：

  • 最后插入一个元素？筛选它直到堆条件成立
  • 将最后一个元素交换到开头？快速向下直到堆条件成立
  • 更改了条目的键？根据变化的方向向上或向下筛选

• 概念简单：由于其隐式数组表示，任何知道基本索引方案（2i+1，2i+2是i的子项）的人都可以实现二进制堆，而无需考虑许多困难的特殊情况。
  如果你在二叉搜索树中查看这些操作，理论上它们也很简单，但是树必须显式存储，例如使用指针，并且大多数操作需要重新平衡树 以保持 O(log n) 高度，需要复杂的旋转（红黑树）或分裂/合并节点（B 树）

• 编辑：存储：正如 Irleon 指出的那样，要存储 BST，您还需要更多的存储空间，因为除了值本身之外，每个条目至少需要存储两个子指针，这可能是一个很大的存储开销，尤其是对于小值类型。同时，堆不需要额外的指针。

回答您关于排序的问题：BST 按顺序遍历需要 O(n) 时间，构造过程需要 O(n log n) 操作，如前所述，这些操作要复杂得多。

同时，Heapsort 实际上可以通过在 O(n) 时间内从输入数组构建一个最大堆，然后重复交换最大元素到 tbe 并缩小堆来就地实现。您可以将堆排序视为具有有用数据结构的插入排序，它可以让您在 O(log n) 时间内找到下一个最大值。

Answer 2

如果排序方法包括将元素存储在数据结构中并在以排序方式提取之后，那么，尽管两种方法（堆和 bst）具有相同的渐近复杂度 O(n log n)，但堆往往更快。原因是堆始终是一个完美平衡的树，并且其操作始终是 O(log n)，以确定性方式，而不是平均而言。对于 bst，根据平衡方法，无论使用哪种平衡方法，插入和删除往往比堆花费更多的时间。另外，堆通常用存储树的层级遍历的数组来实现，而不需要存储任何类型的指针。因此，如果您知道元素的数量（通常是这种情况），则堆所需的额外存储空间将小于 bst 所使用的存储空间。

在对数组进行排序的情况下，有一个非常重要的原因，它宁愿使用堆而不是 bst：您可以使用相同的数组来存储堆；无需使用额外的内存。