Section 4 - Heapsort, Again
8B.4.1 Wanting an In-Place Heapsort
We approached heapSort differently than our other sorts. We were studying the priority queue data structure and found that a binary heap solved that problem for us. Along the way, we noticed that the orderHeap() method, used by the vector-receiving constructor of our binary heap, had a very fast running time, and we exploited that fact to produce an NlogN sorting algorithm when we weren't even looking for one. Isn't it interesting how the world works.
I encourage you to review the derivations done at the end of the module on binary heaps since you are in the mood to do Big-Oh computations. It might mean more to you now.
The bottom line is that we already know the worst case running time of a heapSort, and even have a program/data structure that will do it for us.
Here is a client that uses the vector-receiving constructor of our binary heap.
FHbinHeap<int> my_heap(fhVectorOfInts);
for ( k = 0; k < fhVectorOfInts.size() ; k++ )
fhVectorOfInts[k] = my_heap.remove();
The only qualification of that solution is that, unlike our sorting algorithms this week, the heapSort requires that we include and use a binary heap data structure template file, and build the data structure as part of the algorithm.
It is so easy-to-use, we might opt not to do the work and just advise our clients to use this sort as-is. The only problem is, we would not get to have the fun of converting it to an "in-place" sort. Also, it does require twice the memory, so there is always that excuse.
8B.4.2 Converting the Binary Heap Code
The client loop above, does half (over half, actually) of its work in the constructor, building the heap. That is the first line, where the constructor is invoked. Then, the heap is dissolved slowly in the loop, capturing the items in increasing order. Our heapSort has to emulate both of those aspects.
Deconstructing the Constructor
We grab the code in the constructor, and see what it does:
template <class Comparable>
FHbinHeap<Comparable>::FHbinHeap( const FHvector<Comparable> & items )
: mSize(items.size())
{
int k;
// find the first perfect tree size > items.size() and INIT_CAPACITY
for (mCapacity = INIT_CAPACITY;
mCapacity <= mSize;
mCapacity = 2 * mCapacity
)
{
if (mCapacity < 0)
mCapacity = mSize + 1; // give up - overflow, and not perfect
}
mArray.resize(mCapacity);
// copy starting with position 1 - no ordering yet
for(k = 0; k < mSize; k++ )
mArray[k+1] = items[k];
// order the heap
orderHeap();
}
We see it consists of three parts:
- Determining the size of our internal mArray based on the size of the client items vector. (If you recall, I made this step a little harder than it had to be by insisting on a perfect binary tree size).
- Copying the client vector into our mArray, being careful to avoid location 0.
- Calling orderHeap() which enforced the heap-order property.
Since our goal is to not use any extra memory other than what the client gives us, steps 1 and 2 are now gone. For step 3 (and anything beyond), we will be using the client array as if it were our old mArray.
To emulate the constructor, then, let's peer inside orderHeap() keeping two things in mind:
- The client vector will be used rather than mArray.
- Our client vector starts at 0, not at 1, as did mArray.
Here is orderHeap() exactly as it appears in FHbinHeap.h:
template <class Comparable>
void FHbinHeap<Comparable>::orderHeap()
{
int k;
for(k = mSize/2; k > 0; k-- )
percolateDown(k);
}
For our purposes, we'll need a public driver called heapSort(), and this function will take a client vector. One of the first things we want is a version of percolateDown() that does not assume all the private members or FHbinHeap class, but works using a vector which we will pass to it. Whatever vector the client passes to us, we will pass down to our new percolateDown(). Let's start to write our public driver now, with this in mind.
template <typename Comparable>
void heapSort(FHvector<Comparable> & inArray)
{
int k, arraySize;
// order the array using percolate down
arraySize = inArray.size();
for(k = arraySize/2; k >= 0; k-- )
percolateDown(inArray, k, arraySize);
// second part of the code not considered yet
}
We now have a start. We are getting inArray from the client and passing it down to our new, stand-alone, version of percolateDown() (which we have not written yet). So far, the differences are minor:
- We can start with arraySize/2 just as we did before, but we must go all the way to 0, because the client array has data in inArray[0].
- percolateDown() gets the vector as a parameter, an anticipated consequence of the stand-alone nature of this sort algorithm (we are "sorting in place")
- PercolateDown() also gets the size of the vector as a parameter. This seems like an optional "efficiency" move since the function could have used inArray.size() internally, to figure out the size, but we will soon see that we actually need to pass this parameter for the code to come soon.
Emulating the remove() Loop
Rather than dipping into percolateDown(), let's finish off the public driver under the assumption that percolateDown() works. In the client model at the top of this page, we have a loop that removes the smallest item from the heap and puts it back into the next client vector location. But what does remove() consist of? To save you the trouble of looking back at that module, here is the germ of FHbinHeap::remove():
minObject = mArray[1]; mArray[1] = mArray[mSize--]; percolateDown(1);
minObject is then returned as the minimum value. So we are taking out and returning the root of the tree, moving the old last item of the tree (mArray[mSize]) into the root position, then percolating it down until it finds the correct location. Don't forget the very important mSize-- operation, since that is what cuts off the old location mSize which, as a result of mSize--, ceases to be part of the tree. Our plan, now, is to take minObject and move it into the newly vacated location mSize. Here, then, is where we are replacing the remove()-ed item back into the client array, as I said we would, earlier.
What we just described is the last part of the public heapSort() function, which we now show in its entirety:
template <typename Comparable>
void heapSort(FHvector<Comparable> & inArray)
{
int k, arraySize;
// order the array using percolate down
arraySize = inArray.size();
for(k = arraySize/2; k >= 0; k-- )
percolateDown(inArray, k, arraySize);
// now remove the max element (root) and place at end of array
for(k = arraySize - 1; k > 0; k-- )
{
mySwapFH(inArray[0], inArray[k]); // "remove" by placing at end of array
percolateDown( inArray, 0, k ); // k represents the shrinking array size
}
}
From this vantage point we see that swapping items in position 0 and k accomplishes both the remove()-al of the root of the tree into its new, final, home, and also duplication of the last item into the root position, which preps it for the ensuing percolateDown(). We can also see now why we will need the arraySize parameter in percolateDown(): we will be calling it repeatedly using the same array and need a means to tell it "only operate on the first k elements of this array. don't touch the latter part which holds our sorted elements!"
Adjusting percolateDown()
The original percolateDown():
template <class Comparable>
void FHbinHeap<Comparable>::percolateDown(int hole)
{
int child;
Comparable tmp;
for( tmp = mArray[hole]; 2 * hole <= mSize; hole = child ) // line A-1
{
child = 2 * hole; // LINE A-2
// if 2 children, get the lesser of the two
if( child < mSize && mArray[child + 1] < mArray[child] ) // LINE B
child++;
if( mArray[child] < tmp ) // LINE C
mArray[hole] = mArray[child];
else
break;
}
mArray[hole] = tmp;
}
Adjustment A
The first adjustment is that child = 2*hole + 1 in our new version, rather than 2*hole in the original. Here's why. Consider this tree representation of a binary heap:
a
/ \
b c
/\
d e
The old version used a 1-based array:
0 1 2 3 4 5 6 ...
a b c d e
The left child of a is a position 2*1 = 2 (b is there); the left child of b is at position 2*2 = 4 (d is there), etc. So 2*hole works for this situation. But in our current 0-based array, we have:
0 1 2 3 4 5 6 ... a b c d e
The left child of a is a position 2*0 + 1 = 1 (b is there); the left child of b is at position 2*1 + 1 = 3 (d is there), etc. So 2*hole + 1 is what we need now.
This accounts for the change in what I call // line A-1 and // line A-2.
Adjustment B
The old loop looks for a right child by testing that the left child is not the last element in the array (position mSize). This is in // LINE B. But now the last element is is arraySize - 1 because we have a normal 0 to size-1 array. So the inner test for a left child will become:
if ( child < arraySize - 1 && ... )
This accounts for the first change in line B
In that same condition, we used to be looking for the lesser of the two children (if there were two). Now, however, we use max heap, meaning that the root of each subtree is greater than its two children. So we reverse the test in that line to become:
if ( ... && inArray[child] < inArray[child + 1] )
This accounts for the second change in line B
Adjustment C
Again, because we are doing max heap, we reverse the test that determines if we found the correct position.
if ( tmp < inArray[child] )
This accounts for the change in what I call // line C.
Now we apply all the changes.
template <typename Comparable>
void percolateDown(FHvector<Comparable> & inArray, int hole, int arraySize)
{
int child;
Comparable tmp;
for( tmp = inArray[hole]; 2 * hole + 1 < arraySize; hole = child ) // LINE A-1
{
child = 2 * hole + 1; // LINE A-2
// if 2 children, get the GREATER of the two (because MAX heap)
if( child < arraySize - 1 && inArray[child] < inArray[child + 1]) // LINE B
child++;
if( tmp < inArray[child] ) // LINE C
inArray[hole] = inArray[child];
else
break;
}
inArray[hole] = tmp;
}
With the exception of the obvious implementation of mySwapFH(), we are done.
8B.4.3 A Comparisons
A comparison of the heap sort in its original, bin heap, data structure form with the new sort-in-place heap sort shows that there is no major difference. A Windows and Mac comparison:
// Windows ----------------------------------------------------- // 200000 bin heap template Elapsed Time: 0.017 seconds. heap sort Elapsed Time: 0.016 seconds. // Mac ---------------------------------------------------------- // 200000 bin heap template Elapsed Time: 0.128422 seconds. heap sort Elapsed Time: 0.121768 seconds. // 400000 bin heap template Elapsed Time: 0.273503 seconds. heap sort Elapsed Time: 0.259028 seconds. // 800000 bin heap template Elapsed Time: 0.596064 seconds. heap sort Elapsed Time: 0.544643 seconds.
The Windows gives a faster absolute time. On both platforms the new version is modestly faster, although not by an order-of-magnitude. This speed increase becomes better as the arrays get larger.
In case you want to play with the client on your own, have at it:
// Comparison of 2 heapsorts using vectors
#include <iostream>
using namespace std;
#include "Foothill_Sort.h"
#include "FHsort.h"
#include "FHvector.h"
#include "FHbinHeap.h"
#include <time.h>
// --------------- main ---------------
#define ARRAY_SIZE 200000
int main()
{
int k;
int arrayOfInts[ARRAY_SIZE];
FHvector<int> fhVectorOfInts1;
FHvector<int> fhVectorOfInts2;
clock_t startTime, stopTime;
// build both an array and a vector for comparing sorts
for (k = 0; k < ARRAY_SIZE; k++)
{
arrayOfInts[k] = rand()%ARRAY_SIZE;
fhVectorOfInts1.push_back(arrayOfInts[k]);
fhVectorOfInts2.push_back(arrayOfInts[k]);
}
startTime = clock(); // ------------------ start
FHbinHeap<int> my_heap(fhVectorOfInts1);
for ( k = 0; k < ARRAY_SIZE; k++ )
fhVectorOfInts1[k] = my_heap.remove();
stopTime = clock(); // ---------------------- stop
cout << "bin heap template Elapsed Time: "
<< (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
<< " seconds." << endl;
startTime = clock(); // ------------------ start
heapSort(fhVectorOfInts2);
stopTime = clock(); // ---------------------- stop
cout << "heap sort Elapsed Time: "
<< (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC
<< " seconds." << endl << endl;
for (k = 0; k < ARRAY_SIZE; k+= ARRAY_SIZE/5)
{
cout << "bin heap template #" << k << ": " << fhVectorOfInts1[k] << ", ";
cout << "heap sort #" << k << ": " << fhVectorOfInts2[k] << endl;
}
return 0;
}