I made a promise,
I keep my promise.
Wish my best wish,
to come true.
// We do not use the first element of the array.
// It's more easy to calculate the child index.
// every time this function called, current will be set into the proper position.
template<typename value_type>
void adjust(value_type *array, int current, int length)
{
int large_index = start;
int child = 2*start;
while (child <= length)
{
// firstly, find the larger node's index
if (array[large_index] < array[child]) // left first,
{
large_index = child;
}
if ( (child+1 < length) && (array[large_index] < array[child+1]) ) // then right
{
large_index = child+1;
}
// then, check we need adjust current node?
if (current != large_index)
{
// swap the current and the larger element, and reinitialize current and child.
swap(array[current], array[large_index]);
current = large_index;
child = 2*current;
}
else // Good job done!
{
break;
}
}
}
template<typename value_type>
void CreateHeap(value_type *array, int length)
{
for (int i=length/2; i>0; --i)
{
adjust(array, i, length);
}
return;
}
template<typename value_type>
void HeapSort(value_type *array)
{
int length = array[0];
CreateHeap(array, length);
while (length>0)
{
swap(array[1], array[length]);
--length;
adjust(array, 1, length);
}
}
