JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Heap sort requires O(1) storage, not O(N) as the article says | Reply
The article fails to mention that amongst all sorting methods with guaranteed O(N*log N) complexity, heapsort is the only which requires O(1) storage, but says that it requires O(N)! And just because author used Java in example code, and it is not possible to get effective and versatile containers in Java.
Here is in-place heapsort. Also, the code is *MUCH* shorter.
make_heap(x,x+n);
for(int i=n;i>1;i--)
	pop_heap(x,x+i);
Re: Heap sort requires O(1) storage, not O(N) as the article says (response to post by alliumnsk) | Reply
You say it's O(1) because you reused the array to make the heap. However, when you pop a number, where do you store it?

Even in that approach, you need O(N) to store the sorted array.
Re: Heap sort requires O(1) storage, not O(N) as the article says (response to post by mogers) | Reply
When you pop a number, you free one cell at your heap (stored as a linear array after having heapified it). This cell can be reused to store the elements you pop, one by one in order, so you end up sorting the whole array in-place.

The animation here is pretty, http://en.wikipedia.org/wiki/Heapsort
Re: Heap sort requires O(1) storage, not O(N) as the article says (response to post by mogers) | Reply
pop_heap(x,x+i) does the following:
* temp := x[0];
* from heap in x[0..i-1], x[0] is removed and the heap is popped
* x[i-1] := temp;
obviosuly storing a number needs O(1) space
Re: Heap sort requires O(1) storage, not O(N) as the article says (response to post by mohamedafattah) | Reply
I know, but why alliumnsk doesn't consider the space of the array of numbers?

He didn't mention O(1) extra space (apart from the array).
The old array is used to store the sorted array, so I would agree with O(1) extra space, but the algorithm still needs O(N) in total.

edit: typos
RSS