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

可以从列表中以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中修改值在概念上要困难得多。

最佳答案

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

在对数组进行排序时，有一个非常重要的原因，它比bst更适合作为堆:您可以使用相同的数组来存储堆；可以使用相同的数组来存储堆。无需使用额外的内存。

关于sorting - 为什么我们通过堆而不是二进制搜索树进行排序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47971807/