Heap class

Heap is a complete binary tree where the root of every subtree is larger than its two children. It is convenient to store a complete binary tree in an array.

Write a templated Heap class that (optionally,) uses a dynamic array to store the elements. This class will also have a member variable called how_many of type int. 

If you decide to use a dynamic array, make sure you have the big three functions.

 

template <typename T>
class Heap
{
public:
    Heap():_how_many(0){}
    void insert(const T& insert_me);    //insert into the heap
    T remove();                         //remove and return top value 
    T top();                            //return the value at the top of heap
    bool is_empty() const;
    int size() const;
    int capacity() const;
    friend ostream& operator << (ostream& outs, const Heap<T>& print_me){
        print_me.print_tree(outs);
        return outs;
    }
    bool verify() const;                //true if tree is verified to be a heap
    T *heap_array();                    //returns a copy of underlying array: 
                                        //  don't forget to delete when done

private:
    static const int CAPACITY = 1000;
    T _heap[CAPACITY]; //static array
    int _how_many; //num used

    void print_tree(ostream& outs = cout) const;
    void print_tree(int root, int level = 0, ostream& outs = cout) const;

    bool verify(int root) const;

    bool is_root(int i) const {return i==0;}
    bool is_leaf(int i) const;
    int parent_index(int i) const;
    int left_child_index(int i)const {return 2*i + 1;}
    int right_child_index(int i) const {return 2*i + 2;}
    int big_child_index(int i) const;
    void swap_with_parent(int i);
};