代码之家 › 专栏 › 技术社区 › Shuklaswag

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

heapsort binary-search-tree binary-tree heap sorting

Shuklaswag · 技术社区 · 8 年前

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

类似地,可以在O(n logn)时间内从列表构建二元搜索树,因为将元素插入BST需要平均logn时间,并且有n个元素。

将堆从min遍历到max需要O(n logn)时间(因为我们必须弹出n个元素,每个pop都需要O(logn)sink操作)。从最小值到最大值遍历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要简单得多。
如果需要在创建堆后修改值,则只需应用sink或swim操作。在BST中修改值在概念上要困难得多。

2 回复 | 直到 8 年前

Tobias Ribizel 8 年前

我可以想象,与搜索树相比,您更喜欢(二进制)堆有多种原因:

构造:通过应用 希皮菲 从最小到最大的子树进行自下而上的操作。
修改:二进制堆的所有操作都非常简单:
- 是否在末尾插入元素?筛选它,直到堆条件保持不变
- 是否将最后一个元素交换到开头?将其向下快速移动,直到堆条件保持不变
- 是否更改了条目的键?根据变化的方向上下筛选
概念简单:由于其隐式数组表示,二进制堆可以由任何了解基本索引方案的人实现( 2i+1 , 2i+2 是我 )没有考虑许多困难的特殊情况。
如果你在二叉搜索树中观察这些操作,理论上它们也很简单,但树必须显式存储,例如使用指针,并且大多数操作都要求树 重新平衡 要保持O(对数n)高度,需要复杂的旋转(红黑树)或拆分/合并节点(B-树)
编辑:存储:正如Irleon指出的,要存储BST,还需要更多的存储,因为除了值本身之外,每个条目都需要存储至少两个子指针,这可能是一个很大的存储开销,尤其是对于小值类型。同时,堆不需要额外的指针。

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

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

lrleon 8 年前

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

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