Merge K Sorted Lists
Application of Heap Data Structure

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io
Problem Statement:
You are given an array of k linkedlists lists, each linkedlist is sorted in ascending order.
Merge all the linkedlists into one sorted linkedlist and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linkedlists are:
[ 1>4>5, 1>3>4, 2>6 ]
merging them into one sorted list:
1>1>2>3>4>4>5>6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Solution:
Prerequisite: Having very good knowledge of Heap data structure. Consider taking a look at the below chapters:
 Heap Fundamentals
 Heap: GetMax()/GetMin(), DeleteMax()/DeleteMin() and Insert()
 Heapify
 Heap Sort
 Priority Queue
This is not a very complex problem. If you find yourself having trouble coming up with the algorithm for this problem, you might first want to work on thinking more critically and systematically, while at the same time making sure that you are thinking in the right direction. What I am trying to say here is: your thinking process is super important for problem solving. Thinking logically and systematically, without getting overwhelmed with the magnitude of complexity of the given problem, is an art. So let's not worry about knowing advanced algorithms and data structures, because most solutions only need commonly used algorithms and data structures. Most complex looking problems have simple solutions. Below is how my thinking process would be if I see this problem for the first time:

Let's suppose we are given N lists. Now what is important to keep in mind is that
these lists are SORTED.
Since all the given lists are sorted, the lowest value in the merged list would be the lowest of
all the first elements of the given N lists.
Suppose, the first element of the m^{th} list turns out to be the lowest.
Now our next objective is to find the second lowest element. Notice that the second lowest element would be the lowest of

the first elements of the (N  1) lists which does not include m^{th} list, because
first element of m^{th} list is the first lowest element,
 the second element of the m^{th} list.

the first elements of the (N  1) lists which does not include m^{th} list, because
first element of m^{th} list is the first lowest element,
We repeat the above procedure until we have processed all the elements in N lists.
We simplify the above algorithm as below:
 So at any point of time, the next lowest element is the lowest of all the first elements of the N lists. Make the second element the first for the list which had the lowest first element. Repeat this until all the elements are processed for all the N lists.
So a big part of the solution is to be able to find lowest (or, minimum) of N elements efficiently. Which data structure would serve our purpose really good here ? Min heap. Retrieving min element from Min Heap is O(1). After every operation like Insertion and Deletion, min element always ends up at the root of the min heap. Insertion and Deletion operations are O(logn), where n = size of heap.
If we keep the first elements from all the lists in a min heap, the root of the min heap will have the min element. Once we remove min we insert the next node of the min node in the min heap.
Below is the implementation of the above algorithm using Min Heap.
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Time Complexity:
O(nlogn) + O(Klogn) = O(Klogn) since K > n.Detailed time complexity analysis is given inline in the code above.
Instructor:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn