title: heap sort C - improper output
body: <p>I'm trying to implement heap sort for an array of 10 elements in ascending order.
  I'm following these steps - </p>
  
  <p><strong>heap_sort(arr,size_array):</strong></p>
  
  <pre><code> build_max_heap(arr)
      for(parent=size_array to 1):
         swap(arr[1],arr[parent])
         size_array = size_array - 1;
         max_heapify(arr,1,size);
  </code></pre>
  
  <p>But my output is totally messed up. 
  I can't figure out where I'm going wrong.</p>
  
  <p>This is my input - </p>
  
  <pre><code>20  15  10  1   15  9   2   6   7   9
  </code></pre>
  
  <p>My build_max_heap output - </p>
  
  <pre><code>20  15  10  7   15  9   2   6   1   9
  </code></pre>
  
  <p>My sorted array is the same as the build_max_heap output - </p>
  
  <pre><code>20  15  10  7   15  9   2   6   1   9
  </code></pre>
  
  <p>What am I doing wrong?</p>
  
  <p>Here's my code:</p>
  
  <pre><code>    void max_heapify(int *arr,int i,int size)
  {
      //i is the index of parent node. 2i is left child, 2i+1 is right
      int left = (2*i)+1;
      int right = (2*i)+2;
      int max;
      int temp;
  
      //check which node is the max, parent or one of its children. store max idx.
      if ((left&lt;=size)&amp;&amp;(arr[left]&gt;arr[i]))
          max = left;
      else
          max = i;
      if ((right&lt;=size)&amp;&amp;(arr[right]&gt;arr[max]))
          max = right;
  
      //swap parent with max.
      if(max!=i)
      {
          temp = arr[max];
          arr[max]=arr[i];
          arr[i]=temp;
          max_heapify(arr,max,size);
      }
  
  }
  
  void build_max_heap(int *arr,int size)
  {
      for(int i = size/2; i&gt;=0; i--)
      {
          max_heapify(arr,i,size);
      }
  }
  
  void heap_sort(int *arr, int size)
  {
      int temp;
      build_max_heap(arr,size);
      int i = size;
      while(size&gt;0)
      {
          //swap
          temp = arr[i];
          arr[i] = arr[0];
          arr[0] = temp;
          //reduce size
          size = size -1;
          //heapify
          max_heapify(arr,0,size);
  
      }
  }
  </code></pre>