// File: Heap_ADT/h
// Array Heap ADT prototypes
// A heap is a tree structure used to implement priority queues

#ifndef Heap_ADT_H
#define Heap_ADT_H

#include <vector>
#include <iostream>

using namespace std;

template <class heapEltType> class HeapADT {

public:

 // Constructor
 HeapADT();
 
 // Get for printing
 vector<heapEltType> getData() const;
 
 // Add an Item to the Binary Heap
 // Pre: The heap is not full
 // Post: Elt is added to the tree in priority order
 void insertToHeap(heapEltType elt);

 // Remove the Top Item of the Heap
 // Pre: The heap is not empty
 // Post: The top element is removed from the heap into Elt & the heap
 //	is rearranged to maintain order
 void removeFromHeap(heapEltType & elt);

 // Find out if the heap is empty
 // Returns: 0==>Empty 	Nonzero==>Not Empty
 int isHeapEmpty();

 void heapPrint() const;
 
 private:

 vector<heapEltType> heap;
 int eltsInHeap;

 // Order the heap after a new element is inserted
 void reheapUp();

 // Order the heap after an element is removed
 void reheapDown();

 // Return the index of a node's parent
 // Returns -1 if the node is the root
 int parentOfNode(int index);

 // Return the index of a node's left child
 // Returns -1 if the left child is NULL
 int leftChild(int index) const;

 // Return the index of a node's right child
 // Returns -1 if the right child is NULL
 int rightChild(int index) const;

 // Return the Index of the larger of a node's children
 // Return -1 if the node has no children
 int maxChild(int index);

 // Swap the 2 arguments
 void swap(heapEltType &x,heapEltType &y);
 
};

template <class heapEltType>
	ostream &operator << (ostream &out,const HeapADT<heapEltType> &TheHeap);

#endif