我有两个heapsort算法.第一个是由我写的,而第二个是从某个网站上获取的.据我所知,两者都有相同的逻辑,但第二个的表现比第一个好.出现这种情况的原因是什么？我能看到的唯一区别是我使用递归,而另一个则迭代地进行递归.这可以单独作为差异化因素吗？
我的代码:
def heapify(arr,i,n):
pivot = arr[i] #the value of the root node
left,right = (i<<1)+1,(i<<1)+2 #indices of the left and right subtree root nodes
if right <= n-1: #if right is within the array, so is left
if arr[left] <= pivot and arr[right] <= pivot:
return #if both are less than the root node, it's already heapified
maximum = left if arr[left] >= arr[right] else right #else find which child has a higher value
arr[maximum],arr[i] = arr[i],arr[maximum] …使用堆排序可以在Θ(log n)时间内对多少个元素进行排序？
当我们进行堆操作时,为了构建堆,我们需要Θ(n)复杂度,然后执行heapsort O(nlog n).我理解这个概念.但是当谈到我们的问题时,我们甚至无法在Θ(log n)时间内构建一堆n个元素.答案是O(1)考虑输入大小n？
我还看到了一个不同的解释,它将复杂度推导为考虑输入大小logn的Θ(log n/log log n).我也不太关注这种方法.那么哪个是正确的答案？为什么？
我正在阅读CLRS,它说的是heapsort
HEAPSORT(A):
BUILD-MAX-HEAP(A);
for (i = A.length; i >= 1; i++)
{
exchange A[1] with A[i];
A.heap-size = A.heap-size - 1;
MAX-HEAPIFY(A,1);
}
MAX_HEAPIFY是O(lg n).这本书说它运行MAX-HEAPIFY n次,因此是O(n lg n)时候了.
但是如果堆的大小缩小了1,那么每次迭代都不应该是这样O(lg n!)吗？
会的lg 1 + lg 2 ... + lg(n-1) + lg (n) = lg(n!),对吧？
我试着看http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and -heap-sort/了解堆和堆排序，但没有发现这一点。
我不明白 max-heapify 的功能。它看起来像一个递归函数，但不知何故，由于树的高度，它以对数时间运行。
对我来说这毫无意义。在最坏的情况下，它不是必须反转每个节点吗？我不知道如何在不反复接触每个节点的情况下完成此操作。
什么是循环不变量,如何使用它们来证明堆排序算法的正确性？
我有一个家庭作业问题说:
问题1:给定数组[22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66]为数组构建最大堆.显示所有步骤而不跳过任何细节.
这是我对在互联网上研究的最大堆的理解:
最大堆是一个可以更容易用二叉树表示的数组,其中父节点总是大于它的子节点,并且"每次添加一个子节点时,你都将它添加到左边,这样每次树增加它的高度时它是一棵完整的树"
我认为这是正确的答案,直到我读到我的作业问题2说:
问题2:使用与问题1中相同的数组,使用Heapsort对数组进行排序.显示所有步骤而不跳过任何细节.
现在我很困惑.也许我回答了问题2 ...
在最大堆中(假设它由数组表示),堆的顶部(即堆中的最大值)与数组中的最后一个元素交换(即堆中最小值之一),删除最后一个元素,然后新的top-of-the-heap元素与其他值交换以恢复到正确的位置.
相反,为什么不删除顶部元素,然后其他元素可以"填充"堆？
辅助空间与堆排序的空间复杂性之间的区别？
正如解释在这里：
如果我们想比较基于空间的标准排序算法，那么辅助空间将比空间复杂性更好。合并排序使用O（n）辅助空间，插入排序和堆排序使用O（1）辅助空间。所有这些排序算法的空间复杂度均为O（n）。
我搜索了堆排序的空间复杂度，发现空间复杂度为O（1）。
我的问题是：
那个解释正确吗？辅助空间和空间复杂度有什么区别？
假设我有一个包含以下内容的列表：
lst = [4,0,8,3,1,5,10]
并且我计划使用堆结构来帮助我检索前 k 个最大数字，其中 k 是用户输入。
我知道堆排序是 O(N log N)，我们首先需要 O(N) 时间将它们放在最小/最大堆中，并且 O(log N) 时间来检索元素。
但是我现在面临的问题是我需要在 O(N log K) 时间内检索前 k 个用户。如果我的 k 是 4，我会：
[10,8,5,4]
作为我的输出。我感到困惑的是，在形成堆的早期阶段，我是否应该堆满整个列表以检索前 k 个元素？
迭代大型数组时，哪种算法更快：堆排序还是归并排序？为什么这些算法中的一种比另一种更快？