Merge K Sorted Lists Using Min Heap in DSA Go - Build from Scratch

Merge K Sorted Lists Using Min Heap

📖 Scenario: Imagine you have multiple sorted lists of numbers from different sources, like sorted logs from different servers. You want to combine all these lists into one big sorted list efficiently.

🎯 Goal: Build a Go program that merges k sorted integer slices into one sorted slice using a min heap.

📋 What You'll Learn

Create a slice of sorted integer slices called lists with exactly 3 sorted slices

Create a min heap structure to help merge the slices

Implement the merging logic using the min heap

Print the final merged sorted slice

💡 Why This Matters

🌍 Real World

Merging sorted logs, combining search results, or processing multiple sorted data streams efficiently.

💼 Career

Understanding heaps and merging algorithms is essential for backend development, data engineering, and systems programming.

1

Create the sorted lists

Create a variable called lists which is a slice of integer slices with these exact sorted slices: []int{1, 4, 7}, []int{2, 5, 8}, and []int{3, 6, 9}.

DSA Go

# Your code here

Hint

Use a slice of slices: [][]int and assign the exact slices given.

2

Define the min heap structure

Define a struct called Item with fields value int, listIndex int, and elementIndex int. Then create a type MinHeap which is a slice of Item. Implement the methods Len(), Less(), Swap(), Push(), and Pop() to satisfy heap.Interface.

DSA Go

lists := [][]int{{1, 4, 7}, {2, 5, 8}, {3, 6, 9}}

// Your code here

Hint

Define Item struct and MinHeap type. Implement all 5 methods exactly as named.

3

Implement the merge logic using the min heap

Create a function mergeKLists that takes lists [][]int and returns a single merged sorted []int. Use the MinHeap to push the first element of each list. Then repeatedly pop the smallest item, append its value to the result, and push the next element from the same list if available.

DSA Go

lists := [][]int{{1, 4, 7}, {2, 5, 8}, {3, 6, 9}}

type Item struct {
    value       int
    listIndex   int
    elementIndex int
}

type MinHeap []Item

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(Item))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}

// Your code here

Hint

Push first elements of each list into the heap. Pop smallest, append to result, then push next element from same list if exists.

4

Print the merged sorted list

Call mergeKLists with lists and print the returned merged slice using fmt.Println.

DSA Go

package main

import (
    "container/heap"
    "fmt"
)

lists := [][]int{{1, 4, 7}, {2, 5, 8}, {3, 6, 9}}

type Item struct {
    value       int
    listIndex   int
    elementIndex int
}

type MinHeap []Item

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].value  0 {
            heap.Push(h, Item{value: lst[0], listIndex: i, elementIndex: 0})
        }
    }

    var result []int

    for h.Len() > 0 {
        item := heap.Pop(h).(Item)
        result = append(result, item.value)

        nextIndex := item.elementIndex + 1
        if nextIndex < len(lists[item.listIndex]) {
            nextItem := Item{value: lists[item.listIndex][nextIndex], listIndex: item.listIndex, elementIndex: nextIndex}
            heap.Push(h, nextItem)
        }
    }

    return result
}

// Call mergeKLists and print the result below

Hint

Call mergeKLists(lists) and print the result with fmt.Println.

Practice

1. What is the main advantage of using a min heap to merge K sorted lists?

easy

A. It uses extra memory to store all elements at once.

B. It sorts each list individually before merging.

C. It efficiently finds the smallest element among the heads of all lists.

D. It merges lists by concatenating them without sorting.

Solution

1. Step 1: Understand the role of a min heap in merging

   A min heap keeps track of the smallest elements efficiently, allowing quick access to the smallest head among K lists.

2. Step 2: Compare other options

   Options B, C, and D do not describe the min heap's role correctly. Sorting individually or concatenating without sorting does not merge sorted lists efficiently.

3. Final Answer:

   It efficiently finds the smallest element among the heads of all lists. -> Option C

4. Quick Check:

   Min heap = efficient smallest element access [OK]

Hint: Min heap always gives smallest element fast [OK]

Common Mistakes:

• Thinking min heap sorts entire lists
• Assuming min heap stores all elements at once
• Confusing min heap with simple concatenation

2. Which Go data structure is best suited to implement a min heap for merging K sorted lists?

easy

A. map

B. linked list

C. array without heap functions

D. slice with container/heap package

Solution

1. Step 1: Identify Go's min heap implementation

   Go uses slices combined with the container/heap package to implement min heaps efficiently.

2. Step 2: Evaluate other options

   Maps and linked lists do not provide heap properties. Arrays without heap functions lack automatic heap behavior.

3. Final Answer:

   slice with container/heap package -> Option D

4. Quick Check:

   Go min heap = slice + container/heap [OK]

Hint: Use container/heap with slice for min heap in Go [OK]

Common Mistakes:

• Using map which has no order
• Using linked list which is slow for heap ops
• Ignoring container/heap package

3. What is the output of merging these 3 sorted lists using a min heap?

list1 = [1, 4, 7]
list2 = [2, 5, 8]
list3 = [3, 6, 9]

medium

A. [1, 3, 5, 7, 9, 2, 4, 6, 8]

B. [1, 2, 3, 4, 5, 6, 7, 8, 9]

C. [9, 8, 7, 6, 5, 4, 3, 2, 1]

D. [1, 4, 7, 2, 5, 8, 3, 6, 9]

Solution

1. Step 1: Understand merging with min heap

   The min heap picks the smallest head element from all lists repeatedly, producing a fully sorted merged list.

2. Step 2: Merge given lists step-by-step

   Starting with heads: 1, 2, 3; pick 1, then 2, then 3, then 4, 5, 6, 7, 8, 9 in order.

3. Final Answer:

   [1, 2, 3, 4, 5, 6, 7, 8, 9] -> Option B

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Min heap merges by always picking smallest next element [OK]

Common Mistakes:

• Concatenating lists without sorting
• Reversing order incorrectly
• Mixing elements from different lists randomly

4. Given this Go snippet for merging K sorted lists, what is the bug?

func mergeKLists(lists [][]int) []int {
    var result []int
    h := &IntHeap{}
    heap.Init(h)
    for _, list := range lists {
        for _, val := range list {
            heap.Push(h, val)
        }
    }
    for h.Len() > 0 {
        result = append(result, heap.Pop(h).(int))
    }
    return result
}

medium

A. Pushing all elements at once loses the benefit of merging sorted lists.

B. Heap is not initialized before pushing elements.

C. Result slice is not declared properly.

D. Heap.Pop returns wrong type.

Solution

1. Step 1: Analyze the merging approach

   The code pushes all elements from all lists into the heap at once, ignoring the sorted order advantage.

2. Step 2: Understand the impact

   This approach works but is inefficient (O(N log N)) instead of O(N log K) by pushing only heads and updating heap dynamically.

3. Final Answer:

   Pushing all elements at once loses the benefit of merging sorted lists. -> Option A

4. Quick Check:

   Push all elements = inefficient merge [OK]

Hint: Push only heads, not all elements at once [OK]

Common Mistakes:

• Ignoring heap.Init call
• Misunderstanding result slice declaration
• Incorrect type assertion on Pop

5. You have K sorted linked lists of varying lengths. How would you efficiently merge them using a min heap in Go to minimize time complexity?

hard

A. Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node.

B. Push all nodes from all lists into the min heap at once, then pop all to get merged list.

C. Concatenate all lists and sort the combined list after.

D. Use a max heap instead of a min heap for merging.

Solution

1. Step 1: Use min heap with heads of each list

   Push only the first node of each list into the min heap to keep track of the smallest current element among lists.

2. Step 2: Pop smallest and push next node

   Pop the smallest node, add it to the merged list, then push the next node from that list into the heap, repeating until all nodes are processed.

3. Step 3: Time complexity advantage

   This approach runs in O(N log K) time, where N is total nodes and K is number of lists, which is efficient.

4. Final Answer:

   Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node. -> Option A

5. Quick Check:

   Push heads + pop/push next = efficient merge [OK]

Hint: Push heads only, then push next nodes dynamically [OK]

Common Mistakes:

• Pushing all nodes at once causing inefficiency
• Using max heap which gives largest element first
• Sorting concatenated list which is slower