title: Priority Queue Heap Implementation
body: <p>I'm writing code to implement a priority queue using a heap. When I enter items into the queue with these priorities in this specific order <code>8 10 4 3 7 6 9 5</code> I get an error once I start popping them out with the <code>get_front()</code> function.</p>
  
  <p>The problem is that an assertion fails for the <code>swap_with_parent()</code> function in the <code>while</code>-loop of the <code>get_front()</code> function . The argument is somehow growing larger than the number of items in the array, many_items. I'll post the entire code, if anybody can spot a problem I'd appreciate it if you could let me know. I apologize in advance for the lack of comments, I hope it's clear enough what I had going on.</p>
  
  <pre><code>// INVARIANT for the PriorityQueue Class:
  //   1. The member variable many_items is the number of items in the
  //      PriorityQueue.
  //   2. The items themselves are stored in the member variable heap,
  //      which is a partially filled array organized to follow the usual
  //      heap storage rules from Chapter 11 of the class notes.
  // NOTE: Private helper functions are implemented at the bottom of this
  // file along with their precondition/postcondition contracts.
  
  #include &lt;assert.h&gt;    // Provides assert function
  #include &lt;iomanip&gt;   // Provides setw
  #include &lt;iostream&gt;  // Provides cin, cout
  #include &lt;math.h&gt;      // Provides log2
  #include "pqueue2.h"
  
  using namespace std;
  
  PriorityQueue::PriorityQueue( )
  {
      heap[CAPACITY];
      many_items=0;
  }
  
  void PriorityQueue::insert(const Item&amp; entry, unsigned int priority)
  {
      if(many_items==0)
      {
          heap[many_items].data= entry;
          heap[many_items].priority= priority;
          many_items++;
      }
      else
      {
          heap[many_items].data= entry;
          heap[many_items].priority= priority;
          unsigned int i= many_items;
          many_items++;
          while(parent_priority(i)&lt;priority)
          {
              swap_with_parent(i);
              i=parent_index(i);
          }
      }
  }
  
  PriorityQueue::Item PriorityQueue::get_front( )
  {
      assert(many_items&gt;0);
      if(many_items==1)
      {
          Item front_value=heap[0].data;
          many_items--;
          return front_value;
      }
      else
      {
          Item front_value=heap[0].data;
          heap[0]=heap[many_items-1];
          unsigned int priority= heap[many_items-1].priority;
          unsigned int k=0;
          while( (k&lt;many_items) &amp;&amp; !is_leaf(k) &amp;&amp; big_child_priority(k)&gt;priority)
          {
              unsigned int j=big_child_index(k);
              swap_with_parent(big_child_index(k));
              k= j; 
          }
          many_items--;
          return front_value;
      }
  }
  
  bool PriorityQueue::is_leaf(size_t i) const
  // Precondition: (i &lt; many_items)
  // Postcondition: If heap[i] has no children in the heap, then the function
  // returns true. Otherwise the function returns false.
  {    
      if(((2*i)+1)&gt;many_items)
          return 1;
      else 
          return 0;
  }
  
  size_t PriorityQueue::parent_index(size_t i) const
  // Precondition: (i &gt; 0) &amp;&amp; (i &lt; many_items)
  // Postcondition: The return value is the index of the parent of heap[i].
  {
      //assert( /*(i&gt;0) &amp;&amp; */(i&lt;many_items));
      return (i-1)/2;
  }
  
  unsigned int PriorityQueue::parent_priority(size_t i) const
  // Precondition: (i &gt; 0) &amp;&amp; (i &lt; many_items)
  // Postcondition: The return value is the priority of the parent of heap[i].
  {
      return heap[ (i-1)/2].priority;
  }
  
  size_t PriorityQueue::big_child_index(size_t i) const
  // Precondition: !is_leaf(i)
  // Postcondition: The return value is the index of one of heap[i]'s children.
  // This is the child with the larger priority.
  {
      assert(!is_leaf(i));
      if((2*i)+2&lt;many_items)
      {
          if(heap[(2*i)+1].priority&gt;heap[(2*i)+2].priority)
          {
              return (2*i)+1;
          }
          else
          {
              return (2*i)+2;
          }
      }
      else
      {
          return(2*i)+1;
      }
  }
  
  unsigned int PriorityQueue::big_child_priority(size_t i) const
  // Precondition: !is_leaf(i)
  // Postcondition: The return value heap[big_child_index(i)].priority
  {
      return heap[big_child_index(i)].priority;
  }
  
  void PriorityQueue::swap_with_parent(size_t i)
  // Precondition: (i &gt; 0) &amp;&amp; (i &lt; many_items)
  // Postcondition: heap[i] has been swapped with heap[parent_index(i)]
  {
      assert( i&gt;0 &amp;&amp; i&lt;many_items);
      OneItemInfo temp_parent=heap[parent_index(i)];
      OneItemInfo temp_child=heap[i];
      heap[i]=temp_parent;
      heap[parent_index(i)]=temp_child;
  }
  </code></pre>