Lab 5: Binary Heap

Objectives

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

Assignment

Using either your array_t class or the STL vector class, provide the implementation of the binheap_t<T> class.

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

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)

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();
  }
}

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:

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
Makefile
source code (.h headers and .cpp source)
~~object code~~ (do a make clean before tar)

How to hand in

See sendlab notes