// Chap 11, pp539 - 540
// Rename this file as Heap.h.

// *********************************************************
// Header file Heap.h for the ADT heap.
// *********************************************************
#include "boolean.h"
const int MAX_HEAP = 50;  // maximum heap size

typedef int keyType;  // desired-type-of-search-key
struct heapItem
{  keyType Key;
   // ... and probably other data members
};  // end struct

typedef heapItem heapItemType;

class heapClass
{
public:
// constructors and destructor:
	heapClass();
   heapClass(const heapClass& H);
   virtual ~heapClass();

// heap operations:
   virtual boolean HeapIsEmpty();
   // Determines whether a heap is empty.
   // Precondition: The constructor has been called.
   // Postcondition: Returns TRUE if the heap is empty;
   // else returns FALSE.

   virtual void HeapAdd(heapItemType NewItem,
								boolean& Success);
   // Inserts an item into a heap.
   // Precondition: The constructor has been called.
   // Postcondition: If the heap was not full, NewItem is
   // in its proper position and Success is TRUE;
   // otherwise Success is FALSE.

   virtual void HeapRemove(heapItemType& RootItem,
									boolean& Success);
   // Retrieves and deletes the item in the root of a heap.
   // This item has the largest search key in the heap.
   // Precondition: The constructor has been called.
   // Postcondition: If the heap was not empty, RootItem
   // is the retrieved item, the item is deleted from the
   // heap, and Success is TRUE. However, if the heap was
   // empty, removal is impossible and Success is FALSE.

protected:
   void RebuildHeap(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.