Merge K Sorted Lists — Heap Visualization

The Problem

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.

Example: Given lists = [[1,4,5],[1,3,4],[2,6]], the merged result is [1,1,2,3,4,4,5,6].

Interactive Visualization

Lists (one per line, comma-separated)

Preset

Speed:

Heap Size

Result Length

Total Elements

Input Lists

Min-Heap

Empty — heap will be populated when algorithm starts

Merged Result

Result will appear here as elements are extracted from the heap

Code

import java.util.PriorityQueuefun mergeKLists(lists: List<List<Int>>): List<Int> {    val heap = PriorityQueue<Triple<Int, Int, Int>>(compareBy { it.first })    for ((i, lst) in lists.withIndex()) {        if (lst.isNotEmpty()) {            heap.add(Triple(lst[0], i, 0))        }    }    val result = mutableListOf<Int>()    while (heap.isNotEmpty()) {        val (value, listIdx, elemIdx) = heap.poll()        result.add(value)        if (elemIdx + 1 < lists[listIdx].size) {            val nextVal = lists[listIdx][elemIdx + 1]            heap.add(Triple(nextVal, listIdx, elemIdx + 1))        }    }    return result}

import heapqdef mergeKLists(lists):    heap = []    for i, lst in enumerate(lists):        if lst:            heapq.heappush(heap, (lst[0], i, 0))    result = []    while heap:        val, list_idx, elem_idx = heapq.heappop(heap)        result.append(val)        if elem_idx + 1 < len(lists[list_idx]):            next_val = lists[list_idx][elem_idx + 1]            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))    return result

Status & Log

Press Step or Play to begin.

How It Works

Key Insight

We need to merge k sorted lists into a single sorted list. At every step, the next element in the merged result must be the smallest among all current heads of the k lists. A min-heap (priority queue) lets us find that minimum in O(log k) time instead of scanning all k heads in O(k).

The Algorithm

Initialize: Push the first element of each non-empty list into the min-heap, along with which list it came from and its index within that list.
Extract min: Pop the smallest element from the heap and append it to the result.
Push next: If the list that this element came from has more elements, push the next element from that list into the heap.
Repeat: Continue until the heap is empty — every element has been placed into the result.

Why a Heap?

Without a heap, finding the minimum across k list heads takes O(k) per extraction, leading to O(N × k) total time. The heap reduces each extraction to O(log k), giving O(N log k) total — a significant improvement when k is large.

Complexity

Time O(N log k)

Space O(k)

Where N is the total number of elements across all lists, and k is the number of lists. Each of the N elements is pushed and popped from the heap exactly once, and each heap operation costs O(log k). The heap holds at most k elements at any time.