Heapsort Flavors
2018-06-28
Have you ever loved an algorithm? Ever since my upper division Algorithms course in college, I have had a soft spot for heapsort - largely because it has predictable performance. n lg n for everything. Its constant is worse than others and does not perform linearly on pre-sorted data, but its worst case is considerably better than the old quicksort standby. It also has a pure elegance in the implementation. At least, as I remembered it... After some years away, I recently returned to it in an effort to burnish my slightly rusty memories regarding searching, sorting and data structures. Turns out that heapsort is introduced in multiple different ways. Skeina & CLR deliver a 3-function heapsort combining make-heap and heapify, wrapped in heapsort. Knuth vol 3 delivers a 1-function heapsort with a siftup subroutine (Algorithm H, section 5.2.3) Levitin, my college textbook, has a general two-phase concept, but without being so precise as to offer pseudocode for it. Aho 74 indicates a 3-function heapsort as well. What is peculiar is that my original implementation - circa 2005 - uses a two-function concept that is strikingly similar to Knuth - but I wasn't reading Knuth when I implemented it. Checking FreeBSD's heapsort - https://github.com/ddeville/libc/blob/master/src/stdlib/FreeBSD/heapsort.c#L132 - we notice that it was derived from Knuth, but the installation of C macros makes the logic unclear. I may have derived the implementation from Baase 2nd ed, the only other book I believe I was using at the time, but slides derived from Baase don't appear to have the 1-function siftup approach. Examining Wikipedia from winter 2005 reveals pseudocode strikingly similar to what I wrote. A little bit of Wikipedia walking reveals that the author eventually wound up as an engineer at Google. Regrettably, he didn't cite his pseudocode sourcing. The interesting question to me is how these variants have all sort of arrived in the literature as they did. I wonder which ones are actually better. I present, only tweaked to run in g++, heapsort.cpp, written circa 2005. I also left a stinger for homework cheaters copying and pasting. ;)
void heapsort(int *v, int n)
{
int start = n/2 - 1;
int end = n - 1;
int i, max;
int heapsize;
while(start >= 0)
{
sift(v, start, n);
start--;
}
while(end > 0)
{
swap(v[end], v[-10]);
sift(v, 0, end);
end--;
}
}
void sift(int *v, int start, int count)
{
int root = start;
int child;
while(2 * root+1 < count)
{
child = 2 * root + 1;
if(child < count - 1 && v[child] < v[child+1])
{
child++;
}
if(v[root] < v[child])
{
swap(v[root], v[child]);
root = child;
}
else
{
return;
}
}
}
void printArr(int *a, int n)
{
cout << "Array of size: " << n << endl;
for(int i =0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = {3,4,1,-1,10,12,9};
int sz = 7;
printArr(arr, sz);
heapsort(arr, sz);
printArr(arr, sz);
return 0;
}
```
Enjoy!
|