Section 4 - Order Heap and the Array Constructor
7A.4.1 The Vector Constructor
We will discuss the interesting constructor that takes a vector (unordered) as a parameter. The general idea is that we first use the size of the vector as a guide to create the proper size heap. Once we have created the heap, we copy the array into the internal mArray, shifting everything right one, to avoid location 0. So far, pretty easy.
The only thing is this: we have a complete mess from the standpoint of ordering. The tree is filled out properly, but the heap order is correct practically nowhere. We will create a separate function, orderHeap() whose job it is to take a randomly ordered tree that has heap structure (but not heap order) and makes its order correct. We don't actually pass a heap as a parameter to orderHeap() since it will be a private instance method, and therefore use the this object as its heap.
Assuming, then, that orderHeap() is available for us to use (it will be soon), here is the constructor:
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();
}
The sizing of the internal array is identical in function to that of the default constructor. Everything else is as I said, so we can dispense with further discussion and cut to the chase. How do we write orderHeap()?
7A.4.2 orderHeap()
First look:
template <class Comparable>
void FHbinHeap<Comparable>::orderHeap()
{
int k;
for(k = mSize/2; k > 0; k-- )
percolateDown(k);
}
Holy Smokes. It's so simple. But why does it work?
This is a very elegant and subtle algorithm. It works on the following premise:
percolateDown() RequirementpercolateDown() will do the right thing at a given tree node if the two sub-trees below it are both heap-ordered.
That's how we designed and used it. We took a somewhat random value from the bottom of the tree and dropped it into the root. The tree was ordered already below that root, and percolateDown() simply adjusted the tree to accommodate the node at the root, finding its correct place and making a few adjustments along the way.
Now, however, we have a mess of a tree. The key is, to start with the second-from-bottom level of the tree and perform percolateDown() operations on each node. These nodes are roots of trees that have, at most, three nodes total: the node itself and zero, one or two children. Since individual child nodes vacuously satisfy heap order, nodes in this second-from-bottom layer are perfect candidates for using percolateDown(). Furthermore, after we have applied percolateDown() to every node in the second lowest layer, all these nodes are then heap ordered, so we can move up to the next higher layer and do the same thing. When done with that layer, we move up again, and repeat. We are ordering the heap from bottom to top, one node-at-a-time.
A little thought will reveal that mSize/2 is the correct node to start the process, and we move left and up, one-node-at-a-time until we get to the root.
This is an expensive operation, but we only do it once when we have to create a binary min-heap from a vector.
Why, by the way, do we even anticipate this type of constructor? When will we use it? It plays a prominent role when we get to heap sort, a very fast and elegant sort that makes use of the characteristics of heaps to sort a random array.
7A.4.3 A Sample Client
Finally, we demonstrate a binary heap using a simple client.
// CS_2C Binary Heap Client
#include <iostream>
#include <string>
#include "FHbinHeap.h"
using namespace std;
int main()
{
// first set of tests --------------------
FHbinHeap<string> heap;
string s1 = "nureyev", s2 = "ailey", s3 = "nijinsky";
heap.insert(s1);
heap.insert(s1);
heap.insert(s2);
heap.insert(s2);
heap.insert(s3);
heap.insert(s3);
try
{
while (true)
cout << "removed " << heap.remove() << endl;
}
catch (FHbinHeap<string>::HeapEmptyException)
{
cout << "heap empty\n\n";
}
// second set of tests --------------------
FHbinHeap<string> heap2;
string substrate =
"asdlkfj asdoiBIUYVuwer slkdjLJfwoe89)B)(798rjMG0293lkJLJ42lk3j)(*";
string str_array[500];
unsigned int k, limit;
substrate = substrate + substrate;
for (k = 0; k < substrate.length() - 6; k++)
str_array[k] = substrate.substr(k, 5);
limit = k;
for (k = 0; k < limit; k++)
heap2.insert(str_array[k]);
cout << "\n#strings generated: " << limit
<< "\n#elements in heap: " << heap2.size() << endl;
try
{
while (true)
cout << "removed " << heap2.remove() << endl;
}
catch (FHbinHeap<string>::HeapEmptyException)
{
cout << "heap empty\n\n";
}
return 0;
}
Here is the output. Study the above client and following output to make sure you understand how the heap is used.
removed ailey removed ailey removed nijinsky removed nijinsky removed nureyev removed nureyev heap empty #strings generated: 124 #elements in heap: 124 removed asdo removed asdo removed slkd removed slkd removed (*asd removed (798r removed (798r removed )(*as removed )(798 removed )(798 removed )B)(7 removed )B)(7 removed *asdl removed 0293l removed 0293l removed 293lk removed 293lk removed 2lk3j removed 2lk3j removed 3j)(* removed 3lkJL removed 3lkJL removed 42lk3 removed 42lk3 removed 798rj removed 798rj removed 89)B) removed 89)B) removed 8rjMG removed 8rjMG removed 9)B)( removed 9)B)( removed 93lkJ removed 93lkJ removed 98rjM removed 98rjM removed B)(79 removed B)(79 removed BIUYV removed BIUYV removed G0293 removed G0293 removed IUYVu removed IUYVu removed J42lk removed J42lk removed JLJ42 removed JLJ42 removed Jfwoe removed Jfwoe removed LJ42l removed LJ42l removed LJfwo removed LJfwo removed MG029 removed MG029 removed UYVuw removed UYVuw removed Vuwer removed Vuwer removed YVuwe removed YVuwe removed asdlk removed asdlk removed asdoi removed asdoi removed djLJf removed djLJf removed dlkfj removed dlkfj removed doiBI removed doiBI removed e89)B removed e89)B removed er sl removed er sl removed fj as removed fj as removed fwoe8 removed fwoe8 removed iBIUY removed iBIUY removed j asd removed j asd removed j)(*a removed jLJfw removed jLJfw removed jMG02 removed jMG02 removed k3j)( removed kJLJ4 removed kJLJ4 removed kdjLJ removed kdjLJ removed kfj a removed kfj a removed lk3j) removed lk3j) removed lkJLJ removed lkJLJ removed lkdjL removed lkdjL removed lkfj removed lkfj removed oe89) removed oe89) removed oiBIU removed oiBIU removed r slk removed r slk removed rjMG0 removed rjMG0 removed sdlkf removed sdlkf removed sdoiB removed sdoiB removed slkdj removed slkdj removed uwer removed uwer removed wer s removed wer s removed woe89 removed woe89 heap empty Press any key to continue . . .