为什么递归 heapify 过程的堆排序的空间复杂度是“O(1)”？

Question

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

但堆排序也利用了递归过程，即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) 空间中运行。