title: Why siftDown is better than siftUp in heapify?
body: <p>To build a MAX heap tree, we can either <code>siftDown</code> or <code>siftUp</code>, by sifting down we start from the root and compare it to its two children, then we replace it with the larger element of the two children, if both children are smaller then we stop, otherwise we continue sifting that element down until we reach a leaf node (or of course again, until that element is larger that both of its children).</p>
  
  <p>Now we will only need to do that <code>n/2</code> times, because the number of leaves is <code>n/2</code>, and the leaves will satisfy the heap property when we finish heapifying the last element on the level before the last (before the leaves) - so we will be left with <code>n/2</code> elements to heapify.</p>
  
  <p>Now if we use <code>siftUp</code>, we will start with the leaves, and eventually we will need to heapify all <code>n</code> elements.</p>
  
  <p>My question is: when we use <code>siftDown</code>, aren't we basically doing two comparisons (comparing the element to its both children), instead of only one comparison when using <code>siftUp</code>, since we only compare that element to its one parent? If yes, wouldn't that mean that we're doubling the complexity and really ending up with the same exact complexity as sifting down?</p>