Why space complexity of heap sort is O(1)?

I don't understand how the space complexity of heap sort is O(1)? Though, quick sort doesn't use any extra array (ie in-place), its space complexity is O(n) in worst case and O(lg n) in best case as a stack is used at back end for recursive calls. Am I right?

The same goes with heap sort. Though, it is in-place, but since, Build-Heap function calls Max-Heapify function, so it's space complexity should be equal to Max-Heapify, ie O(lg n). Isn't it? Also, later on Max-Heapify function is called at root node for n times and as I said Max-Heapify() space complexity is O(lg n).

So, overall space complexity of Heap sort should be O(lg n). But I found it O(1) on wikipedia. Help me understand it.

---

Heapsort doesn't take any space that depends on the size of the array being sorted, just the space for the array itself, and a handful of variables. Clearly O (1).

Quicksort keeps track of a stack of subarrays that need sorting. If you are clever and of any two subarrays put the larger one on the stack and sort the smaller one immediately, it takes O (log n).

In practice it doesn't make any difference.

---

Space Complexity refers to the extra space used by the algorithm. Heap Sort doesn't use any extra space ( in O(n) ) except the array to sort. Hence it is O(1)

---

There are non recursive versions of heapify (see example below). For quicksort, if recursion is only used on the smaller partition, then looping back to split what was the larger partition into 2 (again using recursion on the smaller of those 2 partitions and so on), then max stack space is O(log(n)), but worst case time is still O(n^2).

C++ example of non recursive heap sort with non recursive heapify:

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]);
}

链接地址: http://www.djcxy.com/p/40062.html

上一篇: 算法分析

下一篇: 为什么堆排序的空间复杂性是O（1）？