title: Implementing Heap Sort
body: <p>I am attempting to implement Heap sort in my program to learn more about sorting algorithms. However I am running in to an issue.</p>
  
  <p>I call Heap sort in main like this:</p>
  
  <p><strong>Main:</strong></p>
  
  <pre><code>heap_sort(h_vector);
  </code></pre>
  
  <p>Where h_vector is a randomly sized vector with random ordered elements. My heap sort algorithm looks like.</p>
  
  <p><strong>Heap Sort:</strong></p>
  
  <pre><code>void max_heapify(std::vector&lt;int&gt;&amp; v, int i)
  {
      int left = i + 1, right = i + 2;
      int largest;
  
      if( left &lt;= v.size() &amp;&amp; v[left] &gt; v[i])
      {
          largest = left;
      }
  
      else
      {
          largest = i;
      }
  
      if( right &lt;= v.size() &amp;&amp; v[right] &gt; v[largest])
      {
          largest = right;
      }
  
      if( largest != i)
      {
          std::swap(v[i], v[largest]);
          max_heapify(v,largest);
      }
  
  
  
  }
  
  void build_max_heap(std::vector&lt;int&gt;&amp; v)
  {
      for( int i = v.size() - 2; i &gt;= 0; --i)
      {
          max_heapify(v, i);
      }
  
  }
  
  void heap_sort(std::vector&lt;int&gt;&amp; v)
  {
      build_max_heap(v);
      int x = 0;
      int i = v.size() - 1;
      while( i &gt; x)
      {
          std::swap(v[i],v[x]);
          ++x;
          --i;
      }
  
  }
  </code></pre>
  
  <p>Whenever I add this sort to my program I get the following error.</p>
  
  <p><strong>Error:</strong></p>
  
  <pre><code>*** glibc detected *** ./a.out: free(): invalid next size (normal): 0x096c82d0 ***
  </code></pre>
  
  <p>I am not sure what could be causing this. I thought at first that my alogrithm might be going out of bounds of the vector but I have checked a few times and I do not see where. Any ideas? Thanks for your help in advance.</p>