JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Sorting Tutorial Heap sort requires O(1) storage, not O(N) as the article says
 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
 Forums Tutorial Discussions Sorting Tutorial Heap sort requires O(1) storage, not O(N) as the article says Previous Thread  |  Next Thread