// heap.h   ADT for a min-heap   P. Conrad CISC220 06J
// includes features for test-driven development (tdd)

#ifndef HEAP_H
#define HEAP_H

#include "runTests.h"

#include <iostream>
using std::ostream;
using std::cout;
using std::endl;

class Heap_C
{
 public:
  static const int maxSize=1024;
  Heap_C(); // create empty heap
  
  void add(int x); // O(log n)
  int deleteMin(); // O(log n)

  bool isEmpty() const {return (count==0);}     // O(1)
  bool isFull() const {return (count==maxSize);} // O(1)

  void testPrivateMemberFunctions(RunTests_C & test); // for tdd

  void print(ostream & out = cout) const;
  
 private:
  int data[maxSize]; // allocate data on heap
  int count; // initially zero; counts portion of data array containing data

  // restore min-heap property to the heap rooted at rootIndex
  void heapify(int rootIndex);

  // restore min-heap property by bubbling up a value that might violate it
  void bubbleUp(int rootIndex);
  
  // functions to map indices to parent, left child, and right child

  int parentOf(int i) const { if (i==0) return 0; return (i-1)/2; } ;
  int leftChildOf(int i) const { return (2 * i) + 1; } ;
  int rightChildOf(int i) const { return 2 * (i + 1); } ;
  
};

ostream & operator << (ostream & left, const Heap_C & right);


#endif