I can not see why the heapsort is considered an inplace sorting algorithm.
I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.
So may be I am misunderstanding the definition of inplace here?
But insertion sort for example it is obvious that it is inplace algorith, i.e. no extra memory needed for the elements.
So why is it considered inplace?
I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.
No. The array is transformed to conform to the heap constraint without using more than O(1) extra memory. (In fact all you need is extra memory sufficient to hold one element of the array, for swap purposes, plus a boolean or two and a loop variable or two).
Ok, on a technicality it may be that heapsort is usually explained as using a separate heap, but it's perfectly possible to implement it in-place.
You may be missing the fundamental understanding that an array can be used to specify the layout of a tree.
Suppose you have a binary tree, and an interior node is at index i of the array. Then the array index of the parent and children of that node can be found by:
Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1
See:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
Since the heap can be kept and organised entirely in an array, then heapsort can run in-place by moving elements around inside the input array. Indeed, the heap is built and manipulated using the original input array.
If, as you say, one really needed an extra structure to build the heap then heapsort would indeed NOT be an inplace sorting algorithm.
However, this is not the case. You can build the heap on the very same array you wanna sort, and after that you apply the heapsort algorithm, so it sorts inplace.
In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
It is considered in place because it's space requirements are negligible (constant or none at all if you're using bitwise operations to swap items). MergeSort, for example, is not in place because the input set is not modified in each iteration of the search example.
The best way to illustrate the differences between in-place algorithms and out-of-place algorithms is probably to look at the following C/C++ string reversal code that does it in place (from K&R):
void reverse(char s[])
{
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
If you were, for example, reading the input string from the end and placing the characters in another buffer, it would be an out-of place string reversal algorithm.
