// *********************************************************
// Header file Heap.h for the ADT heap.
// *********************************************************
// Must define MAX_HEAP before compilation
//const int MAX_HEAP = maximum-size-of-heap;
const int MAX_HEAP = 10;
#include "HeapException.h"
#include "KeyedItem.h" // definition of KeyedItem
#include <iostream>


typedef KeyedItem HeapItemType;

class Heap
{
public:
   Heap(); // default constructor
	virtual ~Heap();
   // copy constructor and destructor are
   // supplied by the compiler

// Heap operations:
   virtual bool heapIsEmpty() const;
   // Determines whether a heap is empty.
   // Precondition: None.
   // Postcondition: Returns true if the heap is empty;
   // otherwise returns false.

   virtual void heapInsert(const HeapItemType& newItem);
   // Inserts an item into a heap.
   // Precondition: newItem is the item to be inserted.
   // Postcondition: If the heap was not full, newItem is
   // in its proper position; otherwise HeapException is
   // thrown.

   virtual void heapDelete(HeapItemType& rootItem);
   // Retrieves and deletes the item in the root of a heap.
   // This item has the largest search key in the heap.
   // Precondition: None.
   // Postcondition: If the heap was not empty, rootItem
   // is the retrieved item, the item is deleted from the
   // heap, and the function returns true. However, if the
   // heap is empty, removal is impossible and the function
   // throws HeapException.

protected:
   void heapRebuild(int root);
   // Converts the semiheap rooted at index root
   // into a heap.

private:
   HeapItemType items[MAX_HEAP]; // array of heap items
   int          size;            // number of heap items
}; // end class
// End of header file.