title: Max Heapify algorithm results
body: <p>I've been playing around with some of the Algorithms in the Intro to Algorithms textbook, in specific I'm trying get a Binary Heap to work 100% correctly. I have a curious feeling that the example that I'm working with isn't correct, and I was wondering if anyone can help point me in the right direction. </p>
  
  <p>Given the array</p>
  
  <pre><code>int[ ] arr = { 1, 2, 3, 4, 7, 8, 9, 10, 14, 16 };
  </code></pre>
  
  <p>The result I get from MaxHeapify is</p>
  
  <pre><code>[ 16, 14, 9, 10, 7, 8, 3, 1, 4, 2 ]
  </code></pre>
  
  <p>However, after doing a few Google searches, I found that people who use this exact array as an example expect the result to be:</p>
  
  <pre><code>[ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]
  </code></pre>
  
  <p>What confuses me is that the result that my MaxHeapify method gives satisfies the Heap property, but it's different than what is expected. Below is my implementation in Java</p>
  
  <pre><code>public static void BuildMaxHeap( int[ ] arr )
  {
      for( int i = (int)Math.floor( arr.length - 1 ); i &gt;= 0; i-- )
          MaxHeapify( arr, i );
  }
  public static void MaxHeapify( int[ ] arr, int i )
  {
      int left = 2 * i + 1;
      int right = 2 * i + 2;
      int largest = i;
  
      if( left &lt; arr.length &amp;&amp; arr[ left ] &gt; arr[ largest ] )
          largest = left;
      if( right &lt; arr.length &amp;&amp; arr[ right ] &gt; arr[ largest ] )
          largest = right;
      if( largest != i )
      {
          int temp = arr[ i ];
          arr[ i ] = arr[ largest ];
          arr[ largest ] = temp;
          MaxHeapify( arr, largest );
      }
  }
  </code></pre>