#define LEFT(x) (2*(x))
#define RIGHT(x) (2*(x)+1)
#define PARENT(x) ((x)/2)

struct heapEntry {
  int priority;
  int id; // Indicates which item the priority applies to
};
typedef struct heapEntry heapEntryType;

class minHeap
{
public:
  bool full();

  bool empty();

  int getPriority(int id);

  void changePriority(heapEntryType iEntry);

  void insert(heapEntryType iEntry);

  void deleteId(int id);

  heapEntryType minimum();

  heapEntryType extractMin();

  minHeap(int capacity);

  minHeap(int capacity,int priorityIn[],int count);
  // Constructs a heap using the provided priorities.
  // priorityIn[i] will have id i in the constructed heap,
  // so handle[i] may be used to track it.

  minHeap();

  ~minHeap();

private:
  int maxSub;           // Maximum number of elements that heap may hold.
  int n;                // Actual entries in the heap.
  heapEntryType *heap;  // Element 0 is not used
  int *handle;          // Subscripts must be in the range 0..maxSub-1

  void heapify(int j);

  void swapUp(int j);
};