为什么堆排序的空间复杂度为O（1）？

Question

我不明白堆排序的空间复杂度是怎样的O（1）？虽然快速排序不使用任何额外的数组（即就地），但在最坏情况下其空间复杂度为O（n），在最佳情况下为O（lg n），因为在递归调用的后端使用堆栈。我说得对吗？

堆排序也是如此。虽然，它是就地的，但是由于Build-Heap函数调用Max-Heapify函数，所以它的空间复杂度应该等于Max-Heapify，即O（lg n）。不是吗？此外，稍后在根节点调用Max-Heapify函数n次，正如我所说的Max-Heapify（）空间复杂度为O（lg n）。

所以，堆排序的整体空间复杂度应该是O（lg n）。但是我在维基百科上找到了它O（1）。帮助我理解它。

Answer 1

heapify有非递归版本（参见下面的示例）。对于快速排序，如果递归仅用于较小的分区，则循环返回以将较大的分区拆分为2（再次在这2个分区中较小的分区上使用递归，依此类推），则最大堆栈空间为O（log（n）），但最坏的情况时间仍然为O（n^2）。

C使用非递归堆排序的非递归堆排序示例：

typedef unsigned int uint32_t;

void HeapSort(uint32_t *, size_t);
void Heapify(uint32_t *, size_t);
void SiftDown(uint32_t *, size_t, size_t);

void HeapSort(uint32_t * a, size_t count)
{
size_t end;
    Heapify(a, count);      // create initial heap
    end = count-1;
    while(end > 0){
        // swap root (largest value) with end
        std::swap(a[0], a[end]);
        // reduce size of heap and
        // increase size of sorted array
        end--;
        // repair the reduced heap
        SiftDown(a, 0, end);
    }
}

// create initial heap: for root = (count-2)/2 -> 0
// parent = root, children = root*2+1, root*2+2
// swap so that all a[parent] > a[child]
void Heapify(uint32_t * a, size_t count)
{
size_t root;
    if(count < 2)
        return;
    // create sub-heaps of increasing size,
    // with root going from (count-2)/2 to 0
    root = (count - 2) / 2;
    while(1){
        SiftDown(a, root, count-1);
        if(root == 0)
            break;
        root--;
    }
}

// scan from root to end, swapping as needed to repair or create heap
void SiftDown(uint32_t * a, size_t root, size_t end){
size_t parent;
size_t child;
    // while at least two children
    for(parent = root; (child = parent * 2 + 2) <= end; ){
        // choose the larger child
        if(a[child-1] > a[child])
            child = child-1;
        // if child > parent then swap, parent = child
        if(a[child] > a[parent]){
            std::swap(a[child], a[parent]);
            parent = child;
        // else done with search for swaps
        } else {
            break;
        }
    }
    // check for final only child
    if((child = parent * 2 + 1) <= end)
        if(a[child] > a[parent])
            std::swap(a[child], a[parent]);
}

Answer 2

空间复杂性是指算法使用的额外空间。堆排序不使用任何额外空间（在O（n）中），除了数组进行排序。因此它是O（1）

Answer 3

堆排序不占用任何取决于正在排序的数组大小的空间，只占用数组本身的空间和少数变量。显然是O（1）。

快速排序跟踪需要排序的子数组堆栈。如果您很聪明，并且在任何两个子数组中，将较大的一个子数组放在堆栈上，并立即对较小的一个子数组进行排序，则需要O（log n）。

实际上，这没有任何区别。