Merge k Sorted Lists

Q: Apa kompleksitas waktu dari Merge k Sorted Lists?

Dengan min-heap, kompleksitasnya adalah O(N log k) , dengan N sebagai jumlah total nilai dan k sebagai jumlah list. Setiap nilai dimasukkan dan dikeluarkan sekali, dan heap menampung paling banyak k entri. Memori tambahan yang digunakan adalah O(k) , di luar output.

Q: Mengapa tidak menyatukan semua nilai lalu mengurutkannya?

Itu benar dan membutuhkan waktu O(N log N) . Cara ini mengabaikan bahwa list sudah terurut, sehingga membutuhkan log N untuk setiap nilai, sedangkan heap hanya membutuhkan log k , dan semua nilai harus tersimpan di memori sekaligus. Heap juga dapat menggabungkan list yang datang sebagai stream.

SulitHeap Linked list

+10

Kamu mendapatkan k list bilangan bulat sebagai baris-baris dari lists. Setiap baris diurutkan dalam urutan tidak menurun, panjang baris bisa berbeda, dan tidak ada baris yang kosong.

Gabungkan semuanya menjadi satu list yang memuat setiap nilai dari semua baris, diurutkan dalam urutan tidak menurun, lalu kembalikan list tersebut. Nilai yang muncul beberapa kali, dalam satu baris atau beberapa baris, muncul sebanyak itu juga dalam hasilnya.

Fungsi

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: list yang sudah diurutkan, satu per baris, dengan panjang yang mungkin berbeda-beda
Mengembalikaninteger-array: setiap nilai dari semua baris, dalam satu list yang diurutkan

Batasan

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, dan semua baris secara keseluruhan memuat paling banyak 10⁴ nilai
-10⁴ ≤ lists[i][j] ≤ 10⁴
Setiap baris diurutkan secara tidak menurun.

Contoh

Input: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Output: [1, 2, 3, 4, 5, 6, 9, 10]
Penjelasan: Baris-baris dimulai dengan 2, 1, dan 3, jadi 1 muncul lebih dulu. Setelah itu, elemen pertama pada baris-baris tersebut adalah 2, 4, dan 3, jadi 2 muncul berikutnya, dan seterusnya. Baris ketiga habis setelah 5, menyisakan 6, 9, dan 10.

Input: lists = [[5], [-2, 5, 7], [0, 5]]
Output: [-2, 0, 5, 5, 5, 7]
Penjelasan: Ketiga angka 5 berasal dari tiga baris yang berbeda dan ketiganya tetap ada. Angka negatif -2 diurutkan sebelum 0.

Pertanyaan lanjutan

Temukan rentang terkecil [a, b] yang memuat nilai dari setiap baris. Bisakah heap berisi nilai awal setiap baris ditambah nilai awal terbesar melakukannya dalam O(N log k)?

Solusi

Setiap baris sudah diurutkan, jadi nilai terkecil yang belum digunakan selalu menjadi nilai pertama yang belum digunakan pada salah satu baris, yaitu bagian awalnya. Memindai semua k bagian awal memerlukan k langkah untuk setiap dari N nilai. Min-heap yang berisi bagian awal akan memberikan nilai terkecil dalam O(log k), sehingga totalnya berubah dari O(N·k) menjadi O(N log k).

Bandingkan semua kepala k untuk setiap nilai

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Pertahankan indeks pos[r] di awal setiap baris. Setiap putaran membaca semua indeks awal, menambahkan nilai terkecil, lalu memajukan indeks baris tersebut: langkah penggabungan pada merge sort, diperluas dari dua list menjadi k list. Pada contoh pertama, indeks awalnya adalah 2, 1, dan 3, jadi 1 dikeluarkan dan indeks awal baris kedua menjadi 4.

Setiap dari N nilai memerlukan satu kali pemeriksaan terhadap semua k baris. Dengan 10^4 baris yang masing-masing berisi satu nilai, jumlahnya adalah 10^8 pemeriksaan baris.

Algoritma

Tetapkan pos[r] = 0 untuk setiap baris dan hitung jumlah nilainya, N.
Ulangi sebanyak N kali: periksa setiap baris yang pos[r]-nya masih berada di dalam baris tersebut, lalu ingat baris yang elemennya paling kecil.
Tambahkan elemen tersebut ke hasil dan tambahkan 1 ke pos baris itu.
Kembalikan hasilnya.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

Min-heap dari k head

Intuisi

Setelah setiap pengambilan, hanya satu nilai awal yang berubah, tetapi pemindaian membaca ulang semua k. Min-heap menjaga nilai terkecil di posisi teratas. Beri tag pada setiap nilai awal dengan barisnya, sehingga setelah mengeluarkan (value, row), kamu tahu nilai berikutnya dari baris mana yang harus dimasukkan. Heap selalu menyimpan satu entri untuk setiap baris yang masih memiliki nilai, sehingga nilai teratasnya adalah nilai terkecil yang belum digunakan.

Pada contoh pertama, heap dimulai dengan 2, 1, dan 3. Keluarkan 1, masukkan 4. Keluarkan 2, masukkan 6. Keluarkan 3, masukkan 5. Keluarkan 4, masukkan 10. Keluarkan 5: baris ketiga sudah habis, jadi tidak ada yang dimasukkan. Keluarkan 6, masukkan 9, lalu keluarkan 9 dan 10.

Setiap nilai masuk dan keluar sekali, dan heap tidak pernah menyimpan lebih dari k entri: 2N operasi dengan kompleksitas O(log k). Dengan N = k = 10^4, jumlahnya kurang dari 3 × 10^5 langkah. Heap menggunakan memori O(k).

Algoritma

Masukkan (lists[r][0], r) untuk setiap baris r ke dalam min-heap yang diurutkan berdasarkan nilai.
Selama heap tidak kosong, keluarkan pasangan terkecil (value, r) dan tambahkan value ke hasil.
Jika baris r memiliki nilai berikutnya, masukkan nilai tersebut bersama r.
Kembalikan hasil setelah heap kosong.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

Jebakan dan kasus tepi

Memasukkan nilai saja. Setelah pop, kamu tidak bisa mengetahui baris mana yang harus dilanjutkan. Simpan baris bersama nilainya.
Tanpa sengaja menggunakan max-heap. C++ priority_queue dan Rust BinaryHeap menempatkan nilai terbesar di posisi teratas. Gunakan greater<> atau Reverse.
Memasukkan semua nilai di awal. Hasilnya tetap terurut, tetapi heap akan membesar hingga N entri dan pekerjaan menjadi O(N log N).
Membaca melewati akhir baris yang pendek. Pada contoh pertama, baris ketiga memiliki dua nilai, jadi periksa apakah ada nilai berikutnya sebelum memasukkannya.
Menghilangkan nilai duplikat. Tiga nilai 5 pada contoh kedua adalah nilai yang terpisah, dan semuanya harus masuk ke hasil.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Merge k Sorted Lists?

Dengan min-heap, kompleksitasnya adalah O(N log k), dengan N sebagai jumlah total nilai dan k sebagai jumlah list. Setiap nilai dimasukkan dan dikeluarkan sekali, dan heap menampung paling banyak k entri. Memori tambahan yang digunakan adalah O(k), di luar output.

Mengapa tidak menyatukan semua nilai lalu mengurutkannya?

Itu benar dan membutuhkan waktu O(N log N). Cara ini mengabaikan bahwa list sudah terurut, sehingga membutuhkan log N untuk setiap nilai, sedangkan heap hanya membutuhkan log k, dan semua nilai harus tersimpan di memori sekaligus. Heap juga dapat menggabungkan list yang datang sebagai stream.

Bisakah kamu menggabungkan k list yang sudah diurutkan tanpa heap?

Ya, dengan cara bagi dan taklukkan. Gabungkan daftar secara berpasangan menggunakan penggabungan dua daftar, lalu gabungkan hasilnya secara berpasangan, dan seterusnya: log k putaran yang masing-masing menyentuh setiap nilai satu kali, sehingga O(N log k). Menggabungkan daftar satu per satu ke dalam hasil yang terus membesar lebih lambat, O(N·k), karena nilai-nilai awal disalin lagi pada setiap penggabungan.

def mergeKLists(lists):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Output yang diharapkan

[1, 2, 3, 4, 5, 6, 9, 10]