algorithm - 如何计算堆排序的空间复杂度

Question

我知道堆排序的空间复杂度为 O(1)。但是对于计算空间复杂度的递归程序，它的深度也很重要，即它进行的递归调用次数。因此，相同代码的迭代和递归方法的空间复杂度不同。那么当递归处理时，堆排序的空间复杂度是多少？

Answer 1

当使用递归实现 heapify 函数时，它看起来像这样的伪代码:

heapify(arr, n, root): 
    largest = root 
    left = 2*root + 1 
    right = 2*root + 2
    if left < n && arr[left] > arr[largest]: largest = left
    if right < n && arr[right] > arr[largest]: largest = right 
    if largest != root:
        swap(arr[root], arr[largest])
        heapify(arr, n, largest)

回想一下，heapify 函数用于首先将数组变成堆，然后用减小大小的堆对数组进行排序。

重要的是要注意递归模式归结为 tail recursion .根据语言能力，这可以在不使用调用堆栈的情况下执行(其中使用的空间随着每次递归调用而增加)。

因此，除非递归算法还定义了如何递归调用应该“在引擎盖下”实现——可能排除尾递归机制——，它仍然可以是用 O(1) 空间实现。

如果不使用尾递归，则应考虑递归深度。该深度最多为(堆)树的深度，即 logn。