The purpose of the heap is to give you the minimum, so I'm not sure what the purpose of this for-loop is - `for j := 2 to k`. My take on the pseudo-code: lists[k][?] // input lists c = 0 // index in result result[n] // output heap[k] // stores index and applicable list and uses list value for comparison // if i is the index and k is the list // it has functions - insert(i, k) and deleteMin() which returns i,k // populate the initial heap for i = 1:k // runs O(k) times heap.insert(0, k) // O(log k) while !heap.empty() // runs O(n) times i,k = heap.deleteMin(); // O(log k) result[c++] = lists[k][i] i++ if (i < lists[k].length) // insert only if not end-of-list heap.insert(i, k) // O(log k) The total time complexity is thus $O(k * \log k + n * 2 \log k) = O(n \log k)$ You can also, instead of `deleteMin` and `insert`, have a `getMin` ($O(1)$) and an `incrementIndex` ($O(\log k)$), which will reduce the constant factor, but not the complexity.