Since we have to insert all elements of all input arrays in to Heap, wouldn’t the time complexity still be N*Log(N)?

There are N elements in total (from all K arrays) and we have to insert each of then in to the Heap.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively

Lesson: Merge K Sorted Lists (medium) - Grokking the Coding Interview: Patterns for Coding Questions