title: siftUp and siftDown operation in heap for heapifying an array
body: <p>Assume MAX-HEAPIFY operation. where the parent element value is greater than its child values.</p>
  
  <blockquote>
    <ul>
    <li><p>siftDown swaps a node that is too small with its largest child (thereby moving it down) until it is at least as large as both nodes
    below it.</p></li>
    <li><p>siftUp swaps a node that is too large with its parent (thereby moving
    it up) until it is no larger than the node above it. The buildHeap
    function takes an array of unsorted items and moves them until it they
    all satisfy the heap property.</p></li>
    </ul>
  </blockquote>
  
  <hr>
  
  <blockquote>
    <p>There are two approaches one might take for buildHeap. One is to start
    at the top of the heap (the beginning of the array) and call siftUp on
    each item. At each step, the previously sifted items (the items before
    the current item in the array) form a valid heap, and sifting the next
    item up places it into a valid position in the heap. After sifting up
    each node, all items satisfy the heap property. The second approach
    goes in the opposite direction: start at the end of the array and move
    backwards towards the front. At each iteration, you sift an item down
    until it is in the correct location.</p>
  </blockquote>
  
  <p>Let the array a has 5 elements a[4,2,3,5,6] .</p>
  
  <p><strong><em>siftUp</em></strong>-</p>
  
  <p><strong><em>input- a[4,2,3,5,6]</em></strong></p>
  
  <p>processing-</p>
  
  <p>Applying siftUp opearation from the beginning of the array. </p>
  
  <p><em>siftUp(4)</em>-<br>
  no swap as its is the root  </p>
  
  <pre><code> heapified Array-a[4]
  </code></pre>
  
  <p><em>siftUp(2)</em>- </p>
  
  <p>no swap as parent value(4) is more   </p>
  
  <pre><code>heapified Array-a[4,2]
  </code></pre>
  
  <p><em>siftUp(3)</em>-</p>
  
  <p>no swap as parent value(4) is more</p>
  
  <pre><code>heapified Array-a[4,2,3]
  </code></pre>
  
  <p><em>siftUp(5)</em>-</p>
  
  <p>its parent value is 2 so swap (5,2).</p>
  
  <pre><code>          Array-a[4,5,3,2]
  </code></pre>
  
  <p>now 5's parent value is 4 so again swap (5,4).</p>
  
  <pre><code> heapified Array-a[5,4,3,2]
  </code></pre>
  
  <p><em>siftUp(6)</em>-</p>
  
  <p>first swap between (6,4) then between (6,5)</p>
  
  <pre><code> heapified Array-a[6,5,3,2,4]
  </code></pre>
  
  <p><strong><em>output-a[6,5,3,2,4]</em></strong></p>
  
  <p><strong><em>siftDown-</em></strong></p>
  
  <p><strong><em>input- a[4,2,3,5,6]</em></strong></p>
  
  <p>Processing-</p>
  
  <p>From end of the array we will be applying siftDown operation one by one.</p>
  
  <p><em>siftDown(6)</em>- </p>
  
  <p>It has no child so no swap. The same applied for siftDown(5) and siftDown(3) also as they dont have any child.So they cant move further down.</p>
  
  <p>Array till now - a[4,2,3,5,6]</p>
  
  <p><em>siftDown(2)</em>-</p>
  
  <p>It gets swapped with the larger child value. Here 6 is the larger one. so swap (2,6).</p>
  
  <p>Now Array wil be -a[4,6,3,5,2]</p>
  
  <p><em>siftDown(4)</em>-</p>
  
  <p>4 has two child 6 and 3. swap with the larger one. swap (4,6) done.
  Now Array will be- a[6,4,3,5,2]</p>
  
  <p>Again 4 has to be swapped because it has a child which is greater than itself, which is 5 . so swap (4,5) is done.</p>
  
  <p>Array will be - a[6,5,3,4,2]</p>
  
  <p>Heapified array -a[6,5,3,4,2]</p>
  
  <p><strong><em>Output-a[6,5,3,4,2]</em></strong></p>
  
  <p>why am I getting two different outputs when doing siftUp and siftDown operation on same set of elements? Or it is possible to have different heaps when siftUp and siftDown applied to the same set of elements. Please clarify. :)</p>