Merge k Sorted Lists

Introduction

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Things you should know

1. Heap

A heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, for any given node i, the value of i is less than or equal to the values of its children, which ensures that the smallest element is always at the root. You can easily guess what a max-heap would look like. Heaps are commonly used to implement priority queues because they allow efficient access to the smallest or largest element. Basic operations include:

Heapify: convert an unordered list into a heap.
Push: add a new element to the heap.
Pop: remove and return the smallest (or largest) element.
Peek: return the smallest (or largest) element without removing it.

2. Priority Queue

A priority queue is an abstract data type similar to a regular queue or stack, but where each element has a "priority" associated with it. Elements are dequeued in order of their priority, so the element with the highest priority is removed first. Priority queues can be implemented using heaps. In Python, the heapq module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It supports operations like:š

heapify: convert a list into a heap.

import heapq

numbers = [5, 7, 9, 1, 3]
heapq.heapify(numbers)
print(numbers)  # Output: [1, 3, 9, 7, 5]

heappush: add an element to the heap while maintaining the heap property.

heapq.heappush(numbers, 4)
print(numbers)  # Output: [1, 3, 4, 7, 5, 9]

heappop: remove and return the smallest element from the heap.

smallest = heapq.heappop(numbers)
print(smallest)  # Output: 1
print(numbers)   # Output: [3, 5, 4, 7, 9]

heappushpop: push an element onto the heap and then pop the smallest element.

smallest = heapq.heappushpop(numbers, 2)
print(smallest)  # Output: 2
print(numbers)   # Output: [3, 5, 4, 7, 9]

heapreplace: pop the smallest element and push a new element.

smallest = heapq.heapreplace(numbers, 6)
print(smallest)  # Output: 3
print(numbers)   # Output: [4, 5, 6, 7, 9]

3. heapq vs PriorityQueue

Both heapq and PriorityQueue in Python can be used to implement priority queues, but they have some differences:

heapq
- heapq is a module that provides a collection of heap queue algorithms.
- It uses a list to maintain the heap and provides functions like heappush, heappop, heapify, etc.
- It is not thread-safe, so it should be used with care in multi-threaded applications.
PriorityQueue
- PriorityQueue is a class provided by the queue module.
- It is a thread-safe implementation of a priority queue.
- It provides methods like put, get, and qsize.
- It is more suitable for multi-threaded applications where thread safety is a concern.

Because it is not necessary to consider multi threading in this algorithm solution, we will stick to heapq

Solutions

1. Using heapq(priority queue)

This solution uses heapq to sequentially push nodes into a priority queue, ensuring that the node with the smallest value is always popped from the heap first. This approach simplifies the process of merging the lists.

main.py

from heapq import heappop, heappush
from typing import Optional, List
from data_structures import ListNode


def merge_k_sorted_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    dummy = current = ListNode()

    # Push the head nodes of all non-empty linked lists into the heap
    for i, node in enumerate(lists):
        if node:
            heappush(heap, (node.val, i, node))

    # Extract the smallest node from the heap and push its next node (if any)
    while heap:
        val, idx, node = heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heappush(heap, (node.next.val, idx, node.next))

    return dummy.next