algorithm - 为什么 heapsort 的空间复杂度是 `O(1)` 递归 heapify 过程？

Question

当我阅读归并排序的空间复杂度时，我得到的空间复杂度是O(n+logn)。 O(logn) 是在我们考虑递归过程的堆栈帧大小时计算的。

但是heapsort也用到了递归过程，也就是heapify过程。为什么堆排序的空间复杂度是O(1)？

我正在阅读的代码是

```java

public class HeapSort {
public void buildheap(int array[]){
    int length = array.length;
    int heapsize = length;
    int nonleaf = length / 2 - 1;
    for(int i = nonleaf; i>=0;i--){
        heapify(array,i,heapsize);
    }
}

public void heapify(int array[], int i,int heapsize){
    int smallest = i;
    int left = 2*i+1;
    int right = 2*i+2;
    if(left<heapsize){
        if(array[i]>array[left]){
            smallest = left;
        }
        else smallest = i;
    }
    if(right<heapsize){
        if(array[smallest]>array[right]){
            smallest = right;
        }
    }
    if(smallest != i){
        int temp;
        temp = array[i];
        array[i] = array[smallest];
        array[smallest] = temp;
        heapify(array,smallest,heapsize);
    }
}

public void heapsort(int array[]){
    int heapsize = array.length;
    buildheap(array);

    for(int i=0;i<array.length-1;i++){
        // swap the first and the last
        int temp;
        temp = array[0];
        array[0] = array[heapsize-1];
        array[heapsize-1] = temp;
        // heapify the array
        heapsize = heapsize - 1;
        heapify(array,0,heapsize);
    }   
}

```

Answer 1

您发布的 Java 代码的空间复杂度不是 O(1)，因为它占用了非常量的堆栈空间。

然而，这不是实现堆排序的常用方法。 heapify 方法中的递归可以很容易地替换为简单的 while 循环(无需引入任何额外的数据结构，如堆栈)。如果这样做，它将在 O(1) 空间内运行。