Why the space complexity of heapsort is `O(1)` with a recursive heapify procedure?

Question

When I was reading the space complexity of merge sort, I got the space complexity of that is O(n+logn). O(logn) is calculated when we consider the stack frame size of the recursive procedures.

But the heapsort also utilizes the recursive procedure, which is the heapify procedure. Why the space complexity of heapsort is O(1)?

and the code I am reading is

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

```

I would wager there's a heapify algorithm that isn't recursive. — Mooing Duck, Mar 17 '15 at 01:00
duplicate of : http://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1 — softwarenewbie7331, Mar 17 '15 at 01:17
I have read that url, and I think my problem may be different — GsM, Mar 17 '15 at 01:20
"But the heapsort also utilizes the recursive procedure" What makes you say that? — sepp2k, Mar 17 '15 at 01:48
@GsM It's possible to make an implementation heapsort which uses log(n) stack space, but it's also possible not to. — Paul Hankin, Mar 17 '15 at 01:58

score 5 · Answer 1 · answered Mar 17 '15 at 03:17

The space complexity of the Java code you posted is not O(1) because it consumes a non-constant amount of stack space.

However this is not the usual way to implement heapsort. The recursion in the heapify method can easily replaced by a simple while loop (without introducing any additional data structures like a stack). If you do that, it will run in O(1) space.

score 2 · Answer 2 · answered Mar 17 '15 at 01:43

2

The heapify() function can by implemented tail-recursively. Many functional languages guarantee that tail-recursive functions use a constant amount of stack space.

answered Mar 17 '15 at 01:43

Tavian Barnes

12,477
4
45
118

1

While that's true, it should be pointed out that in the general case a recursive implementation of heapsort or heapify *would* consume non-constant stack space, which is why the usual implementation of the algorithm is not recursive (at least in languages that don't guarantee TCO). – sepp2k Mar 17 '15 at 02:00

Why the space complexity of heapsort is `O(1)` with a recursive heapify procedure?

2 Answers2