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.