1
7
我可以想象,与搜索树相比,您更喜欢(二进制)堆有多种原因:
为了回答您关于排序的问题:BST按顺序遍历需要O(n)个时间,构建过程需要O(n log n)个操作,正如前面提到的,这些操作要复杂得多。 同时,Heapsort实际上可以通过在O(n)时间内从输入数组构建最大堆,然后重复地将最大元素交换回tbe并缩小堆来实现。您可以将Heapsort视为插入排序,它有一个有用的数据结构,可以让您在O(log n)时间内找到下一个最大值。 |
2
3
如果排序方法包括将元素存储在数据结构中,并在以排序方式提取后进行排序,那么,尽管两种方法(堆和bst)具有相同的渐近复杂性O(n log n),但堆往往更快。原因是堆始终是一个完全平衡的树,其操作始终是O(log n),以确定的方式,而不是平均值。对于bst,根据平衡的方法,插入和删除往往比堆花费更多的时间,无论使用哪种平衡方法。此外,堆通常使用存储树的级别遍历的数组来实现,而不需要存储任何类型的指针。因此,如果您知道元素的数量(通常是这样),那么堆所需的额外存储空间将小于bst所使用的存储空间。 在对数组进行排序的情况下,有一个非常重要的原因,那就是宁愿使用堆而不是bst:可以使用相同的数组来存储堆;无需使用额外内存。 |
mourinho · Python中按顺序遍历树返回列表 6 年前 |
Dongho Han · 用C语言中的二叉搜索树查找合计 6 年前 |
Richard Cooper · 使用递归的C++二叉搜索树 6 年前 |
Pranshu · 无法删除二进制搜索树中的根节点 6 年前 |
Vanshaj · 给定的数字序列是否有唯一的二进制搜索树? 6 年前 |
M.Hamra · 如何编写递归函数来返回BST中的最小值? 6 年前 |
Matt · 二进制搜索树遍历方法,以便字符串 6 年前 |
I.Klein · 递归获取二叉搜索树的高度[闭合] 6 年前 |