Why does heap sort have a space complexity of O(1)?
Solution 1
Data in an array can be rearranged into a heap, in place. The algorithm for this is actually surprisingly simple., but I won't go into it here.
For a heap sort, you arrange the data so that it forms a heap in place, with the smallest element at the back (std::make_heap
). Then you swap the last item in the array (smallest item in the heap), with the first item in the array (a largish number), and then shuffle that large element down the heap until it's in a new proper position and the heap is again a new min heap, with the smallest remaining element in the last element of the array. (std::pop_heap
)
data: 1 4 7 2 5 8 9 3 6 0
make_heap: [8 7 9 3 4 5 6 2 1 0] <- this is a min-heap, smallest on right
pop_heap(1): [0 7 9 3 4 5 6 2 1 8] <- swap first and last elements
pop_heap(2): 0 [7 9 3 4 8 6 2 5 1] <- shuffle the 8 down the heap
pop_heap(1): 0 1 [9 3 4 8 6 2 5 7] <- swap first and last elements
pop_heap(2): 0 1 [9 7 4 8 6 3 5 2] <- shuffle the 7 down the heap
etc
So no data actually needs to be stored anywhere else, except maybe during the swap step.
For visualization, here's that original heap shown in a standard form
make_heap
0
2 1
3 4 5 6
8 7 9
pop_heap
8 1 1
2 1 2 8 2 5
3 4 5 6 -> 3 4 5 6 -> 3 4 8 6
7 9 7 9 7 9
Solution 2
The cool trick here is since heap is a full binary tree, you can just use a plain array, and for item i, its parent would be the item i/2
.
Herman Tran
Aspiring web developer. I'm especially interested in all things JavaScript, from front-end MVC frameworks to the server side with Node.js.
Updated on October 20, 2020Comments
-
Herman Tran over 3 years
I understand that both quick sort and merge sort need
O(n)
auxiliary space for the temporary sub-arrays that are constructed, and in-place quick sort requiresO(log n)
auxiliary space for the recursive stack frames. But for heap sort, it seems like it also has a worst case ofO(n)
auxiliary space to build the temporary heap, even if the nodes are just pointers to the actual elements.I came across this explanation :
Only O(1) additional space is required because the heap is built inside the array to be sorted.
But I think this means the original array necessarily already had to be implemented as some sort of tree? If the original array was just a vector, it seems memory for a heap would still have to be allocated.
-
HelloWorld123456789 about 10 years@MooingDuck I agree with you. Although one who knows the answer will figure out in a second.
-
Mooing Duck about 10 years@RikayanBandyopadhyay: "Before you can understand recursion you must first understand recursion"
-
Herman Tran about 10 yearsThanks for the explanation and example!
-
Herman Tran about 10 yearsThank you, this is also helpful
-
Jim Mischel about 10 yearsThis doesn't answer the question at all.
-
Siddhartha over 9 yearsExcellent answer and visualization. Saved!
-
mc9 over 3 yearsNice. It is a cool property that allows us to build a heap inside the array itself to be sorted. I would add that heap can be thought of as a complete binary tree, where all levels except possibly the last are filled, and the nodes are as far to the left as possible. A full binary tree would indicate that the tree is completely filled on all levels.