#ifndef _PQ_H
#define _PQ_H

// templated priority queue class
// written and modified many times
// 11/27/95 
//          to use vector class rather than array type
// 12/30/96
//          changed to use two templated classes, one for
//          item, one for priority (old version had int
//          for priority)
//          also added DeleteMin in two ways: one has
//          parameters to return values when deleting
//
// 11/99    changed to tvector class
// 01/00    one template parameter, can construct with
//          comparer object to change how < works
// 
// 05/00    ap version, only one template parameter, the type
//          must support operator <
//
// operations:
//
// appriority(int)
//     construct pqueue of specified size
//
// void insert(const Kind &)
//     insert Kind object
//
// int size()    const
//     returns the number of elements in the priority queue
//
// bool isEmpty() const
//     returns true if pqueue is empty, otherwise returns false
//
// void deletemin()
//     remove minimal element from queue
//
// void deletemin(Kind &)
//     remove minimal element and return it and its priority
//
// void getmin(Kind &)
//     return minimal element and its priority
//
// Complexity:
//
// a heap-based implementation is used, so minelt is O(1)
// and insert/deletemin are O(log n) where n is # of items in pqueue
// (insert is O(1) average case)
//

#include "apvector.h"

template <class Kind>
class appriority
{
  public:
    appriority();
    ~appriority();
    void insert(const Kind & kind);      // insert kind
    int size()     const;                // return # of elements
    bool isEmpty() const;                // return true iff empty

    void deletemin();                    // remove min elt from 
    void deletemin(Kind &);              // remove/return min elt
    Kind& getmin( );                     // return min elt

    void dump() const;
    
  private:
    void init (int n);                   // reserve space for n elements
    
    void heapify(int vroot);             // percolate down function
    apvector<Kind> myList;                // array of prioritized stuff
    int myNumElts;                       // # elements in priority queue
};

// uncomment line below if including source code (no template.cc)
#include "appriority.cpp"

#endif