Merge N Sorted Linked Lists Using Min Heap
Here, the goal is to benefit from the fact that a min-root heap always returns the smallest member. The initial entry of each linked list is the smallest element in its corresponding list since, in this technique, all the linked lists are already sorted. We take advantage of this circumstance by creating a min-heap out of the initial member of each linked list. The smallest element is then obtained by extracting the top element (root) of the min-heap. We get the smallest element across all linked lists by doing this. The next element is then added to the min-heap after we increase the pointer to the list that the freshly extracted element belongs to. A new element is taken from the min-heap, the linked list pointer that contains it is incremented, and the newly pointed element is then added to the min-heap. Until the min-heap is completely empty, this operation is repeated. Keep in mind that we continuously add the elements that we extract from the min-heap to a separate result list that we are keeping.
The method’s flexibility is a key benefit. With a few minor adjustments, this approach may also be used to combine the N sorted arrays. Some of the other ways fail to do this, but this approach succeeds even when all the linked lists are not the same size.
Algorithm:
Let’s first have a look at the algorithm for this strategy before using an example to clarify it.
1) Create a min-heap and fill it with the first item from each of the “n” linked lists.
2) Repeat the following actions up until the min-heap is complete empty:
- Remove the min-root heap’s element and include it in the result list.
- Add the element to the min-heap if it is in the same linked list and is next to the element that was previously extracted.
3) Return the result list’s head node address.
In order to comprehend the method better, let’s use an example. Let’s say the following linked listings are provided to us:
The element (1) of this min-root heap is popped. In this instance, the item that was popped is from the second linked list. Since it contains a nearby item (item 7), the second linked list’s pointer is modified to refer to item 7, and item 7 is added to the min-heap. The current extracted element 1 is added to the final output array.
The initial element which is 2 is popped and appended to the newly formed linked list. Thus, the pointer of the third linked list is changed to point to the next element which is 7. This element is added to the min-heap because 2 was a member of this linked list.
The number 4 is removed from the min-heap and added to the linked list which is the final linked list outcome. A new element (6) is added to the min-heap, and the pointer of the first linked list is modified to point to it.
The resultant linked list now includes the extracted number 6. Since element Six (6) was previously part of the first linked list. Its pointer is now pointing to the following element (8), and this element is added to the min-heap.
Once again, we take the root node (7) and add it to the min-heap. While the pointer to the second linked list is updated, no new elements are added to the min-heap because there are none in the second linked list.
In this case, the number 7 from the third linked list is popped from the min-heap. Updates are made to the pointer of the third linked list, and the value 29 is added to the minimum heap.
This time, we’re going to pop the number 8 Then, we move the pointer into the first linked list. Again, no new elements are added to the min-heap because there are none left in the first linked list.
The last remaining element in the min-heap, number 29, is removed. The pointer to the third linked list is updated. But since there are already no new elements in the list, none are added.
Now that the min-heap is empty, we can use the linked list that was generated as the merged linked list. This is the final form of the linked list that is produced by this algorithm.
Understand the Concepts with Code and Image
We have three linked lists as shown in the following:
Note: At the start, the min heap is empty.
We add the first elements of all the linked lists into the stack.
{
if (array[i] != NULL)
minheap.push(array[i]);
}
We create a resultant linked list as shown in the image:
struct Node *tempNode = headNode;
The while loop is executed because the minheap is not empty (size = 3 (> 0)).
Here, we extract the top element from the stack and assign it to the resultant tempNode.
struct Node* curr = minheap.top();
minheap.pop();
tempNode->next = curr;
Now, in this code, we allocate the tempNode with the whole linked list of the top element. Element 2 is included with the other connected list members, as can be seen in the following image:
curr -> 2
So, in the previous image, we can see that tempNode is pointing to the curr (top element).
Now, in this step, we have to check whether the current top element has another linked list member or not. If there is still a member, we add that element to the heap.
minheap.push(curr->next);
We add the element number 5 to the stack because the current top element was 2 and its next element is 5.
Again, we follow the previous steps.
The while loop is executed because minheap is not empty (size = 3 (> 0)). Here, we extract the top element from the stack and assign it to the resultant tempNode.
struct Node* curr = minheap.top();
minheap.pop();
tempNode->next = curr;
Again, in this code, we allocate the tempNode with the whole linked list of the top element. Element 3 is included with the other connected list members, as can be seen in the following image:
curr -> 3
Note: The linked list of the previously current top element 2 is overwritten by the linked list of the new top member.
Again, in this step, we check whether the current top element has another linked list member or not. If there is still a member, we add that element to the stack.
minheap.push(curr->next);
We add the element number 4 to the stack because the current top element was 3 and its next element is 4.
Again, we follow the previous steps.
The while loop is executed because the minheap is not empty (size = 3 (> 0)).
Here, we extract the top element from the stack and assign it to the resultant tempNode.
struct Node* curr = minheap.top();
minheap.pop();
tempNode->next = curr;
Again, in this code, we allocate the tempNode with the whole linked list of the top element. Element 4 is included with the other connected list members, as can be seen in the following image. And also, again, in this step, we check whether the current top element has another linked list member or not. If there is still a member, we add that element to the stack.
if (curr->next != NULL)
minheap.push(curr->next);
curr -> 4
We add the element number 6 to the stack because the current top element was 4 and its next element is 6.
Now, element 5 is inserted.
curr -> 5
Now, element 6 is inserted.
curr -> 6
Curr (6)->next == NULL because no element is available after the element 6. So, nothing is added to the heap.
Now, element 7 is added after element 6.
curr -> 7
Now, element 8 is added after element 7.
curr -> 8
Now, element 9 is added after element 8.
curr -> 9
Curr (9)->next == NULL because no element is available after the element 9. So, nothing is added to the heap.
Finally, we add the element 10 in the list.
Now, the heap is empty. So, the loop breaks and we return the headNode.
Implementing the Heap Algorithm for Merging the N Sorted Lists
using namespace std;
struct Node {
int info;
struct Node*next;
};
struct Node*newNode(int info) {
struct Node*new_node= new Node();
new_node->info = info;
new_node->next= NULL;
returnnew_node;
}
//'compare' function used to build
// up the priority queue
struct compare {
bool operator()(
struct Node* a, struct Node* b) {
return a->info > b->info;
}
};
// In this function, we are going to merge N sorted linked lists into one list
struct Node*merge_N_Sorted_LinkedLists(struct Node* array[], int N)
{
//Priority_queue'minheap' implemented with the compare function
priority_queue<Node*, vector, compare> minheap;
// We are pushing all the head nodes of the
// linked list into minheap stack
for (inti=0; inext=curr;
tempNode=tempNode->next;
// Checking top listany member still available ornot
if (curr->next!= NULL)
// Pushing the next node of top node into the minheap
minheap.push(curr->next); }
// Address of head node of the required merged list
returnheadNode->next;
}
// Function to display the linked list
void displayMergeLinkedList(struct Node* head) {
while (head != NULL) {
cout<info <next;
}
}
int main() {
// N Number of linked lists
int N =3;
// An array of pointers that stores the linked list's head nodes
Node* array[N];
array[0] =newNode(2);
array[0]->next=newNode(4);
array[0]->next->next=newNode(6);
array[0]->next->next->next=newNode(8);
array[1] =newNode(3);
array[1]->next=newNode(5);
array[1]->next->next=newNode(7);
array[1]->next->next->next=newNode(9);
array[2] =newNode(1);
array[2]->next=newNode(10);
array[2]->next->next=newNode(11);
array[2]->next->next->next=newNode(12);
struct Node* head =merge_N_Sorted_LinkedLists(array, N);
displayMergeLinkedList(head);
return0;
}
Output:
Conclusion
We learned how to combine the N sorted linked lists into a single sorted linked list in this article. We provided a simple visual example by utilising the min heap to help you comprehend this idea. After that, we also explained it using code and graphics. Since the minimum heap was the foundation of this method, we also attempted to describe how it works in this article. This method has a time complexity of O(n.log(k)) where n is the number of nodes in the list, and k is the total number of lists.
Source: linuxhint.com