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

Question

I don't understand how the space complexity of heap sort is O(1)? Though, quick sort doesn't use any extra array (i.e. 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, i.e. 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.

Quicksort uses O (log n) space unless the implementation is stupid. — gnasher729, Sep 02 '16 at 19:05
Possible duplicate of [Why does heap sort have a space complexity of O(1)?](http://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1) — nits.kk, Sep 02 '16 at 19:06
Heap sort can be accomplished using a fixed amount of additional space apart from the original storage -- the heap itself can be created by swapping values. Hence, it is O(1) in *additional* space needed. — Gordon Linoff, Sep 02 '16 at 19:07
Though it is good to think and reason about anything we read. But equally important good practise is to find solutions to the questions arising in our mind, by searching if there already an answer existing to the question. please refer http://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1 — nits.kk, Sep 02 '16 at 19:08
That question didn't help me much. I know that heap sort doesn't take any extra array. But when Max-Heapify is called, it does take extra space of O(lg n) as in worst case, Max-Heapify can call itself recursively for lg n time, so a recursive stack must be made to store all the function calls. Isn't it? In quick sort too, extra space is used due to recursive calls of Quick-Sort() function, i.e., O(n) in worst case and O(lg n) in best case. — programmer_, Sep 02 '16 at 19:21
@programmer: heapify is iterative; the recursive version is a simple tail call. That's not true of quicksort;to eliminate the recursion, a stack is required. — rici, Sep 03 '16 at 00:11

score 0 · Answer 1 · answered Sep 02 '16 at 19:08

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.

score 0 · Answer 2 · answered Sep 02 '16 at 19:16

0

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)

answered Sep 02 '16 at 19:16

Sai Sriharsha Annepu

82
8

Then how does space complexity of Quick sort is O(log n) in best case and O(n) in worst case. Please, help me understand. As far as I know, quick sort also doesn't use any extra space. – programmer_ Sep 02 '16 at 19:27

score 0 · Answer 3 · answered Sep 02 '16 at 20:47

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

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

3 Answers3