#ifndef _MINHEAP_H
#define _MINHEAP_H

#include <iostream.h>
#include "PQueue.h"

template <class Object, class Compare>
class MinHeap : public PriorityQueue<Object, Compare> {
public:

  MinHeap();                        // Constructor - initializes heap to size 1
  MinHeap(int size);                // Constructor - initializes heap to size
  ~MinHeap();                       // Destructor

  // Const functions

  bool isEmpty(void) const;           // True iff the pqueue is empty
  const Object & findMin(void) const; // Returns unchangeable reference to
                                      // minimum elment. Should _not_ be
                                      // used to alter the minimum
                                      // element in any way.

  // Non-const functions

  void insert(const Object & x);      // Inserts a copy of x into the pqueue
  void deleteMin();                   // Deletes the minimum element from
                                      // the pqueue
  void deleteMin(Object & minItem);   // Deletes the minimum element
                                      // from the pqueue and puts a copy
                                      // of it into minItem.
  void makeEmpty();                   // Deletes all elements from the
                                      // pqueue.

  void buildHeap(Object *x, int size); // The contents of the array at x 
                                       // replace the contents of the 
                                       // current heap to form a new heap.
  void reHeap();                       // fix the heap structure.  If Object
                                       // is a pointer type, if the value an
                                       // an object points to changes, the 
                                       // heap property might be lost.  This is
                                       // an alternative to using increaseKey,
                                       // decreaseKey.  
                                         
private:
  // Helper Functions
  void percolateUp(const Object & x, int hole );
  void percolateDown( int hole );
  void removeMin();  
  void resizeHeap();  

  // An instance of the comparator for comparing elements of the
  // queue.
  const Compare comp;

  Object *array;  // the array of objects
  int max_size;  // max size of the array
  int curr_size;  // current size of the heap

};



#endif