#ifndef _PAIRHEAP_H_
#define _PAIRHEAP_H_

#include "Pair.h"

// A Heap which holds Pairs.  This class is so tightly tied to the
// particular application (since it uses the heapIndex field of
// the Pair struct) that there's no point in making it generic.
class PairHeap {

public:

  PairHeap(int initial_size);
  ~PairHeap();

  void insert(Pair *pair);

  Pair *removeMax(void);

  void updatePair(Pair *pair);

protected:

  void _sift(int index);		// Also called "percolate down"
  void _percolate(int index);

  inline int _parent(int index); // These return the appropriate relations
  inline int _lchild(int index); // of a given index.
  inline int _rchild(int index);

  void _resize(void);		// Resizes the heap to twice its
				// original capacity

  Pair **_heap;
  int _size;			// The capacity of the heap
  int _numElts;			// The number of elements actually in
				// the heap
};

#endif