sorting - 为什么我们通过堆排序而不是二叉搜索树？

Question

从列表构造堆可以在 O(n logn) 时间内完成，因为向堆中插入一个元素需要 O(logn) 时间并且有 n 个元素。

类似地，二叉搜索树可以在 O(n logn) 时间内从列表构造出来，因为向 BST 中插入一个元素平均需要 logn 时间，并且有 n 个元素。

从最小到最大遍历堆需要 O(n logn) 时间(因为我们必须弹出 n 个元素，并且每次弹出都需要 O(logn) 接收操作)。从最小到最大遍历 BST 需要 O(n) 时间(实际上只是中序遍历)。

因此，在我看来，构建这两种结构所需的时间相同，但 BST 的迭代速度更快。那么，为什么我们使用“Heapsort”而不是“BSTsort”呢？

编辑:感谢 Tobias 和 lrlreon 的回答!综上所述，我们使用堆而不是 BST 进行排序的原因如下。

• 堆的构建实际上可以在 O(n) 时间内完成，而不是 O(nlogn) 时间。这使得堆构建比 BST 构建更快。
• 此外，数组可以轻松地就地转换为堆，因为堆始终是完整的二叉树。 BST 不能轻松地实现为数组，因为 BST 不能保证是完整的二叉树。这意味着 BST 需要额外的 O(n) 空间分配来排序，而堆只需要 O(1)。
• 堆上的所有操作都保证是 O(logn) 时间。 BST，除非平衡，否则可能有 O(n) 运算。堆的实现比平衡 BST 简单得多。
• 如果您需要在创建堆后修改某个值，您只需应用接收器或游泳操作即可。修改 BST 中的值在概念上要困难得多。

Answer 1

我可以想象您更喜欢(二进制)堆而不是搜索树有多种原因:

• 构造:通过从最小到最大的子树自下而上应用堆化操作，实际上可以在 O(n) 时间内构造二叉堆。

• 修改:二叉堆的所有操作都相当简单:

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

• 概念简单:由于其隐式数组表示形式，任何了解基本索引方案(2i+1、2i+2 em> 是 i 的 child )，无需考虑许多困难的特殊情况。
  如果你在二叉搜索树中查看这些操作，理论上它们也很简单，但是树必须显式存储，例如使用指针，大多数操作都需要树重新平衡以保留 O(log n) 高度，这需要复杂的旋转(红黑树)或拆分/合并节点(B 树)

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

回答关于排序的问题:BST 需要 O(n) 时间按顺序遍历，构建过程需要 O(n log n) 操作，正如前面提到的，这要复杂得多。

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