CODEWITHSUNDEEP
algorithmsorting
GsM
GsM

Reputation: 161

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

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

```

Upvotes: 1

Views: 1023

Answers (2)

sepp2k
sepp2k

Reputation: 370425

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.

Upvotes: 5

Tavian Barnes
Tavian Barnes

Reputation: 12932

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

Upvotes: 2

Related Questions