title: C++ priority queue as binary heap
body: <p>have been making progress, but still can't figure out where my infinite loop is...</p>
  
  <p><strong>header file:</strong></p>
  
  <pre><code>#include &lt;string&gt;
  
  class priority_queue_overflow{};    //if insert tries to exceed the size of A then throw priority_queue_overflow() 
  class priority_queue_underflow{};   //if extract_min tries is called on an empty heap then throw priority_queue_overflow() 
  
  class priority_queue {
  private:
  
    class pair {
    public:
      std::string object;
      double key;
    };
  
    pair* A;  //the array used to store the heap
    int heapsize; //the current heap size
    int size; //the current size of the array: does not change
  
    void heapify(int k);  //as described in Cormen et al
  
  public:
  
    priority_queue(int n); //don't forget to allocate the array of size n+1 as we don't use slot zero
    ~priority_queue();    //delete the array
  
    bool empty(); //true/false depending upon whether the heap is empty
    void insert(std::string s, double priority); //add s to the heap with the given priority as its key
    std::string extract_min();    //remove the string of lowest key and return that string
  
    operator std::string();
  };
  </code></pre>
  
  <p><strong>cpp file:</strong></p>
  
  <pre><code>/**
   * implementing the priority queue as a binary heap
   *
   */
  
  #include &lt;iostream&gt;
  #include &lt;istream&gt;
  #include &lt;ostream&gt;
  #include &lt;sstream&gt;
  #include &lt;map&gt;
  #include &lt;algorithm&gt;
  
  #include "binary_heap.hpp"
  
  /***********************
   *** inline functions
   ***********************/
  inline int left(int i) { return  2*1; } // ( i &lt;&lt; 1 )
  
  inline int right(int i) { return 2*i+1; } // (i &lt;&lt; 1 | 1)
  
  inline int parent(int i) { return i/2; } // ( i &gt;&gt; 1 )
  
  
  /*********************
   *** constructor
   *********************/
  priority_queue::priority_queue(int n)  //don't forget to allocate the array of size n+1 as we don't use slot zero 
    :heapsize(0), size(n)
  {
    A = new pair[n+1];
  }
  
  
  /*********************
   *** destructor
   *********************/
  priority_queue::~priority_queue()  //delete the array
  {
    delete[] A; // iterrate through delete each elem
  }
  
  
  /*******************************************
   *** heapify * finds max of three things
   *******************************************/
  void priority_queue::heapify(int k)
  {
    std::cout&lt;&lt;"HERE HEAP"&lt;&lt;'\n';
    pair smallest = A[k];
    int pos = k;        
  
    //only treat child as object if it's inside heap
    if (left(k) &lt;= heapsize and A[left(k)].key &lt; A[pos].key) {
  
      // update variables
      smallest = A[left(k)];
      pos = left(k);
    }
  
    // identical for right
    if (right(k) &lt;= heapsize and A[right(k)].key &lt; A[pos].key) {
  
      // update variables
      smallest = A[right(k)];
      pos = right(k);
    }
  
    // after both if's exectued: smallest and pos contain smallest key
  
    // only need to do something if pos is !=i
    std::cout&lt;&lt; pos &lt;&lt;" == "&lt;&lt; k&lt;&lt;'\n';
  
    if (pos != k) {
  
      // swap items
      std::swap(A[k], A[pos]);
  
      // go recursive   
      heapify(pos);
    }
  }
  
  
  /****************
   *** empty
   ****************/
  bool priority_queue::empty()
  {
    return (heapsize == 0);
  }
  
  
  /****************
   *** insert
   ****************/
  void priority_queue::insert(std::string s, double priority)  //add s to the heap with the given priority as its key
  {
    if (heapsize == size) {
      throw priority_queue_overflow();
    }
  
    ++heapsize;  
    A[heapsize].object = s;
    A[heapsize].key = priority;
  
    int i(heapsize);
    while (i &gt; 1 and A[parent(i)].key &gt; A[i].key) {
      std::swap(A[parent(i)], A[i]);
      i = parent(i);  
    }
  }
  
  
  /*******************
   *** extract_min
   *******************/
  std::string priority_queue::extract_min()  //remove the string of lowest key and return that string
  {
    if (heapsize == 0) {
      throw priority_queue_underflow();
    }
  
    std::string ans = A[1].object;
    A[1] = A[heapsize];
    --heapsize;
    heapify(1);
    return ans;        
  }
  
  
  /**********************************
   *** function operator overload
   **********************************/
  priority_queue::operator std::string()
  {
    std::stringstream text; 
    int i(1);  
  
    while (i &lt;= size) { 
      text &lt;&lt; A[i].object &lt;&lt; std::endl;
      ++i;
    } 
    return text.str(); 
  }
  </code></pre>