# Lab 5: Binary Heap

## Objectives

To build a binary heap (and use it to sort with)

## Assignment

1. Using either your `array_t` class or the STL `vector` class, provide the implementation of the `binheap_t<T>` class.
2. Provide the following `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 ```

3. Provide the following `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) ```

4. Your code should be such that the following `main()` routine works unaltered: ```#include <iostream> #include <iomanip> #include <vector> #include <cstdlib> #include <cmath> #include "binheap.h" // prototypes int main(int argc, char **argv); int main(int argc, char **argv) { float no; binheap_t<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(); } } ```
5. Sample output:
```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
```

## Turn in

Turn in all of your code, in one `tar.gz` archive of your lab##/ directory, including:
1. A `README` file containing
1. Course id--section no
2. Name
3. Lab description
4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
5. Lessons learned, identified interesting features of your program
6. Any special usage instructions
2. `Makefile`
3. source code (`.h` headers and `.cpp` source)
4. object code (do a `make clean` before `tar`)

## How to hand in

See `sendlab` notes