可以在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进行排序的要点。
如果排序方法包括将元素存储在数据结构中并在以排序方式提取之后,那么,尽管两种方法(heap和bst)具有相同的渐近复杂度O(n log n),但堆往往更快。原因是堆始终是一个完美平衡的树,其操作始终是O(log n),以确定的方式,而不是平均。使用bst,取决于平衡的标准,无论使用哪种平衡方法,插入和删除往往比堆更多的时间。另外,堆通常用存储树的级别遍历的数组实现,而不需要存储任何类型的指针。因此,如果您知道元素的数量(通常是这种情况),则堆所需的额外存储量小于用于bst的额外存储量。
在对数组进行排序的情况下,有一个非常重要的原因,它更倾向于堆而不是bst:您可以使用相同的数组来存储堆;无需使用额外的内存。
我可以想象您希望在搜索树上更喜欢(二进制)堆的原因有多种:
回答有关排序的问题:BST需要O(n)时间按顺序遍历,构造过程需要O(n log n)次操作,如前所述,这些操作要复杂得多。
同时,Heapsort实际上可以通过在O(n)时间内从输入数组构建最大堆来实现,然后重复交换最大元素以返回并缩小堆。您可以将Heapsort视为插入排序,其中包含一个有用的数据结构,可让您在O(log n)时间内找到下一个最大值。