title: Complexity of heapify on a leftist heap queue
body: <p>"Data Structures and Network Algorithms" by Tarjan states the heapify function in <a href="https://en.wikipedia.org/wiki/Leftist_tree" rel="nofollow noreferrer">leftiest heaps</a> as following:</p>
  
  <pre><code>heap function heapify (list q);
    do |q| ≥ 2 → := q[3..] &amp; meld (q(1), q(2)) od;
    return if q = [ ] → null | q != [ ] → q(1) fi
  end heapify;
  </code></pre>
  
  <p><code>q</code> is being the queue of heaps we would like to heapify together. <code>meld(h1, h2)</code> is being a function for merging two heaps and restoring the heap property. <code>meld(h1, h2)</code> is having the complexity <em>O(logn)</em>, where <em>n</em> is the total number of nodes in both heaps. This makes the complexity for one pass through the queue as following:</p>
  
  <p><a href="https://i.stack.imgur.com/h0kSb.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/h0kSb.gif" alt="enter image description here"></a><strong>(Eq. 1)</strong></p>
  
  <p>which is plausible. What I do not get is the time for the entire heapify as it is:</p>
  
  <p><a href="https://i.stack.imgur.com/ttUXg.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ttUXg.gif" alt="enter image description here"></a><strong>(Eq. 2)</strong></p>
  
  <p><code>k</code> here is the number of original heaps and <code>n</code> the total number of items they contain. There are also two constrains mentioned beforehand:</p>
  
  <p><a href="https://i.stack.imgur.com/utqLE.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/utqLE.gif" alt="enter image description here"></a><strong>(Eq. 3)</strong></p>
  
  <p>Can somebody help me understand how the Eq. 2 is derived? (how one interprets the left expression of the equality in Eq. 2)</p>