-
63 votesanswersviews
为什么不总是使用堆排序[重复]
这个问题在这里已有答案： Quicksort vs heapsort 11个答案 Quicksort superiority over Heap Sort 5个答案 Heap Sort 排序算法似乎具有O（nlogn）的最差情况复杂度，并且使用O（1）空间进行排序操作 . 这似乎比大多数排序算法更好 . 那么，为什么不总是使用Heap Sort作为排序算法（为什么人们使用排序机制，如M... -
1 votesanswersviews
如何证明从竞争二叉树到数组的转换？
complete 二叉树可以有效地实现为数组，其中索引i处的节点具有索引 2i 和 2i+1 处的子节点以及索引 floor(i/2) 处的父节点，具有 one-based indexing . 如果子索引大于节点数，则子项不存在 . 我看到这些转换，但有 no formal proof of them ，可以给出严格的证据或链接，谢谢！ -
5 votesanswersviews
为什么我们通过堆而不是二进制搜索树进行排序？
可以在O（n logn）时间内从列表构造堆，因为将元素插入堆需要O（logn）时间并且有n个元素 . 类似地，可以在O（n logn）时间内从列表构造二叉搜索树，因为将元素插入到BST中需要平均登录时间并且存在n个元素 . 从最小到最大遍历堆需要O（n logn）时间（因为我们必须弹出n个元素，并且每个pop需要O（logn）接收器操作） . 从最小到最大遍历BST需要O（n）时间（字面上只是顺序... -
1 votesanswersviews
堆排序时间复杂性深刻理解
当我在大学学习数据结构课程时，我学到了以下公理： 在最坏的情况下将新数字插入堆需要 O(logn) （取决于作为叶插入时它到达树中的高度） 使用 n 节点构建一堆 n 节点，从空堆开始，使用摊销分析求和为 O(n) 时间 在最坏情况下删除最小值需要 O(logn) 时间（取决于新顶节点在与最后一个叶子交换后达到的低点） 逐个删除所有最小值，直到堆为空，需要 O(nlogn) 时间复...