title: Heapsort Algorithm using min-heap
body: <p>When I implement <code>heapsort</code> using a <code>min-heap</code> it sorts the array from largest to smallest. Is this the desired output for a <code>heapsort</code> using <code>min-heap</code>? It seems redundant to sort again to output smallest to largest after the sort is complete since the <code>heap</code> itself has a smallest to largest structure.</p>
  
  <p>CODE:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include "random.h"
  #include "print.h"
  int parent(int i)
  {
      return (i - 1) / 2;
  }
  int left(int i)
  {
      if(i == 0)
          return 1;
      else
          return 2*i;
  }
  int right(int i)
  {   if(i == 0)
          return 2;
      else
          return 2*i + 1;
  }
  void min_heapify(std::vector&lt;int&gt; &amp;A, int i, int heapsize)
  {
      int smallest;
      int l = left(i);
      //std::cout &lt;&lt; "left = " &lt;&lt; l &lt;&lt; std::endl;
      int r = right(i);
      //std::cout &lt;&lt; "right = " &lt;&lt; r &lt;&lt; std::endl;
      if(l &lt;= heapsize &amp;&amp; A[l] &lt; A[i])
          smallest = l;
      else
          smallest = i;
      //std::cout &lt;&lt; "smallest = " &lt;&lt; smallest &lt;&lt; std::endl;
      if(r &lt;= heapsize &amp;&amp; A[r] &lt; A[smallest])
          smallest = r;
      if(smallest != i) {
          print(A);
          exchange(A, i, smallest);
          min_heapify(A, smallest, heapsize);
      }
  }
  void build_min_heap(std::vector&lt;int&gt; &amp;A)
  {
      int heapsize = A.size() - 1;
      for(int i = (A.size() - 1) / 2; i &gt;= 0; i--)
          min_heapify(A, i, heapsize);
  }
  void heapsort(std::vector&lt;int&gt; &amp;A)
  {
      int heapsize = A.size() - 1;
      build_min_heap(A);
      std::cout &lt;&lt; "heapsort after buildmaxheap" &lt;&lt; std::endl;
      print(A);
      for(int i = A.size() - 1; i &gt; 0; i--) {
          exchange(A, 0, i);
          heapsize--;
          std::cout &lt;&lt; "heapsize = " &lt;&lt; heapsize &lt;&lt; std::endl;
          min_heapify(A, 0, heapsize);
      }
  }
  int main()
  {
      std::vector&lt;int&gt; B;
      fill(B, 5);
      print(B);
      heapsort(B);
      print(B);
      return 0;
  }
  </code></pre>
  
  <p>Output from code:</p>
  
  <pre><code>41 65 31 41 19 
  41 65 31 41 19 
  41 65 19 41 31 
  41 19 65 41 31 
  41 19 31 41 65 
  19 41 31 41 65 
  heapsort after buildmaxheap
  19 31 41 41 65 
  heapsize = 3
  65 31 41 41 19 
  31 65 41 41 19 
  heapsize = 2
  heapsize = 1
  65 41 41 31 19 
  heapsize = 0
  65 41 41 31 19 
  </code></pre>
  
  <p>Output for 20 elements:</p>
  
  <pre><code>41 65 31 41 19 15 72 11 78 69 37 23 29 63 75 4 5 49 75 99 
  after buildmaxheap
  4 5 15 11 19 23 29 41 31 69 37 41 72 63 75 65 78 49 75 99 
  after sort
  99 78 75 75 72 69 65 63 49 41 41 37 31 29 23 19 15 11 5 4 
  </code></pre>