tar.gz
archive of your asg2/ directory, including:
README file containing
Makefile
.h headers and .cpp source)
make clean before tar)
handin notes
Array class or the STL
vector class, provide the implementation
of the binheap<T> class.
public member functions:
int size() const; // return size of heap
bool empty(); // return true if empty
void clear() // clear out the heap, make it empty
void pop(); // alias for deleteMin
const T& top() const; // alias for findMin
void insert(T& el); // insert element
void decKey(int p, T delta); // decrement key at position p
void incKey(int p, T delta); // increment key at position p
private member functions:
void percolateDown(int hole); // used by pop()
void buildheap(); // only needed for constructor
void swap(T& el1, T& el2); // convenience (not really needed)
main()
routine works unaltered:
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
using namespace std;
#include "binheap.h"
// prototypes
int main(int argc, char **argv);
int main(int argc, char **argv)
{
float no;
binheap<float> bh;
srandom((unsigned long)0x1337);
for(int k=0; k<10; k++) {
no = (((float)random()/(float)RAND_MAX) * 10.0);
bh.insert(no);
std::cout << "inserting: " << no << std::endl;
}
std::cout << "Heap:" << std::endl;
std::cout << bh;
std::cout << "incrementing top node's key by 10" << std::endl;
bh.incKey(1,10.0);
std::cout << "Heap:" << std::endl;
std::cout << bh;
while(!bh.empty()) {
std::cout << "deleting min = " << bh.top() << std::endl;
bh.pop();
}
}
inserting: 3.53221 inserting: 4.02488 inserting: 2.06317 inserting: 5.92108 inserting: 4.67547 inserting: 7.14106 inserting: 8.3808 inserting: 2.00877 inserting: 7.09874 inserting: 4.84983 Heap: 1: 2.00877 2: 2.06317 3: 3.53221 4: 4.02488 5: 4.67547 6: 7.14106 7: 8.3808 8: 5.92108 9: 7.09874 10: 4.84983 incrementing top node's key by 10 Heap: 1: 2.06317 2: 4.02488 3: 3.53221 4: 5.92108 5: 4.67547 6: 7.14106 7: 8.3808 8: 12.0088 9: 7.09874 10: 4.84983 deleting min = 2.06317 deleting min = 3.53221 deleting min = 4.02488 deleting min = 4.67547 deleting min = 4.84983 deleting min = 5.92108 deleting min = 7.09874 deleting min = 7.14106 deleting min = 8.3808 deleting min = 12.0088