I'm not sure what it is specifically that you don't understand. Can you
post some code and specificy what it is you're not clear about?
Does this help?
Heap Sort
---------------------------------------------------------------
Algorithm Analysis
The heap sort is the slowest of the O(n log n) sorting algorithms, but
unlike the merge and quick sorts it doesn't require massive recursion
or multiple arrays to work. This makes it the most attractive option
for very large data sets of millions of items.
The heap sort works as it name suggests - it begins by building a heap
out of the data set, and then removing the largest item and placing it
at the end of the sorted array. After removing the largest item, it
reconstructs the heap and removes the largest remaining item and places
it in the next open position from the end of the sorted array. This is
repeated until there are no items left in the heap and the sorted array
is full. Elementary implementations require two arrays - one to hold
the heap and the other to hold the sorted elements.
To do an in-place sort and save the space the second array would
require, the algorithm below "cheats" by using the same array to store
both the heap and the sorted array. Whenever an item is removed from
the heap, it frees up a space at the end of the array that the removed
item can be placed in.
Pros: In-place and non-recursive, making it a good choice for extremely
large data sets.
Cons: Slower than the merge and quick sorts.
Empirical Analysis
Heap Sort Efficiency
As mentioned above, the heap sort is slower than the merge and quick
sorts but doesn't use multiple arrays or massive recursion like they
do. This makes it a good choice for really large sets, but most modern
computers have enough memory and processing power to handle the faster
sorts unless over a million items are being sorted.
The "million item rule" is just a rule of thumb for common applications
- high-end servers and workstations can probably safely handle sorting
tens of millions of items with the quick or merge sorts. But if you're
working on a common user-level application, there's always going to be
some yahoo who tries to run it on junk machine older than the
programmer who wrote it, so better safe than sorry.
Source Code
Below is the basic heap sort algorithm. The siftDown() function builds
and reconstructs the heap.
void heapSort(int numbers[], int array_size)
{
int i, temp;
for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}
void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
---------------------------------------------
The only thing confusing here is the replacement of the largest item
from the array data, to the just-cleared array position, just made up
in that same array.
A fine refinement to have, but it can be confusing for others trying to
understand it.
Adak
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
