Create a template class,
Heap,
with methods
push,
pop,
and
is_empty
that implements the binary heap algorithm as discussed in class.
Create a separate type
Data
to hold the data elements.
This concrete object will be the type parameter used to instantiate
the
Heap
template.
The
Heap
constructor should take a parameter which is a function pointer or
function object that compares two
Data
pointers.
The comparison function should have type signature
bool (*)(Data* left, Data* right)
and return
true
if
left
is higher priority
(less than)
right.
You may
use the STL
vector
container class to hold the data.
To test your algorithm, add a
sort
method that uses the heapsort algorithm, storing the data in place
returning the underlying
vector1.
Since in-place heapsort reverse-sorts the data, you may either use
the
reverse
STL function
or implement your ordering predicate
such that it returns a greater-than instead of less-than.
Your main program should read words (one word per line, per
assignment 1) from standard input and emit
the sorted words to standard output.
You do not need to remove duplicates or count occurrences.
Coincidentally, this is exactly what the
sort
command does,
so you have a convenient way to test your program.