Struktur Bercabang · Pelajaran 8 dari 10
Heap dan priority queue
10 menit baca · BelajarCode
Binary heap adalah pohon biner lengkap yang memenuhi sifat heap: pada min-heap, setiap simpul lebih kecil atau sama dengan anak-anaknya. Akibatnya, elemen terkecil selalu ada di akar.
Disimpan dalam array
Karena pohonnya lengkap (diisi dari kiri, tingkat demi tingkat), heap bisa disimpan dalam array tanpa referensi:
- Anak kiri dari indeks i ada di 2i + 1.
- Anak kanan dari indeks i ada di 2i + 2.
- Induk dari indeks i ada di (i - 1) div 2.
1def tambah(heap, nilai):2 heap.append(nilai)3 i = len(heap) - 14 while i > 0:5 induk = (i - 1) // 26 if heap[i] >= heap[induk]:7 break8 heap[i], heap[induk] = heap[induk], heap[i]9 i = induk101112def ambil_minimum(heap):13 terkecil = heap[0]14 terakhir = heap.pop()15 if heap:16 heap[0] = terakhir17 i = 018 while True:19 kiri, kanan = 2 * i + 1, 2 * i + 220 kecil = i21 if kiri < len(heap) and heap[kiri] < heap[kecil]:22 kecil = kiri23 if kanan < len(heap) and heap[kanan] < heap[kecil]:24 kecil = kanan25 if kecil == i:26 break27 heap[i], heap[kecil] = heap[kecil], heap[i]28 i = kecil29 return terkecil303132h = []33for x in [42, 17, 8, 23, 4, 15]:34 tambah(h, x)35print("Isi array heap:", h)36print("Diambil berurutan:", [ambil_minimum(h) for _ in range(6)])Isi array heap: [4, 8, 15, 42, 23, 17] Diambil berurutan: [4, 8, 15, 17, 23, 42]
- Menambah: taruh di akhir, lalu tukar dengan induknya selama lebih kecil (sift up).
- Mengambil minimum: ambil akar, pindahkan elemen terakhir ke akar, lalu tukar dengan anak yang lebih kecil sampai sifat heap pulih (sift down).
Keduanya O(log n), karena tinggi pohon lengkap adalah log n.
Modul heapq
Python menyediakan heap siap pakai di modul heapq.
1import heapq23pasien = []4heapq.heappush(pasien, (3, "Andi", "demam"))5heapq.heappush(pasien, (1, "Bela", "sesak napas"))6heapq.heappush(pasien, (2, "Citra", "patah tulang"))7heapq.heappush(pasien, (1, "Dimas", "pendarahan"))89while pasien:10 prioritas, nama, keluhan = heapq.heappop(pasien)11 print(f"Prioritas {prioritas}: {nama} ({keluhan})")1213print("Tiga terbesar:", heapq.nlargest(3, [5, 1, 9, 3, 7, 2]))Prioritas 1: Bela (sesak napas) Prioritas 1: Dimas (pendarahan) Prioritas 2: Citra (patah tulang) Prioritas 3: Andi (demam) Tiga terbesar: [9, 7, 5]
Tuple dibandingkan elemen demi elemen, jadi angka prioritas dibandingkan lebih dulu. Untuk prioritas yang sama, nama dibandingkan sebagai penentu.
| Masalah | Peran heap |
|---|---|
| Antrean IGD, penjadwalan proses di sistem operasi | Priority queue |
| Jalur terpendek (algoritma Dijkstra) | Mengambil simpul dengan jarak terkecil |
| k data terbesar dari jutaan data | Menyimpan k kandidat saja |
| Heap sort | Mengurutkan dalam O(n log n) |
Cek pemahaman
Pada heap yang disimpan sebagai array, di indeks berapa anak kanan dari simpul di indeks 3?
Latihan
Gabungkan k list terurut
Gabungkan tiga list terurut [1, 4, 9], [2, 3, 10], dan [5, 6, 7, 8] menjadi satu list terurut memakai heap: masukkan elemen pertama setiap list, lalu setiap kali mengambil minimum, masukkan elemen berikutnya dari list asalnya.
Pembahasan
1import heapq23def gabung_k(daftar_list):4 heap = []5 for i, d in enumerate(daftar_list):6 if d:7 heapq.heappush(heap, (d[0], i, 0))8 hasil = []9 while heap:10 nilai, i, j = heapq.heappop(heap)11 hasil.append(nilai)12 if j + 1 < len(daftar_list[i]):13 heapq.heappush(heap, (daftar_list[i][j + 1], i, j + 1))14 return hasil1516print(gabung_k([[1, 4, 9], [2, 3, 10], [5, 6, 7, 8]]))[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Heap paling banyak berisi k elemen (satu per list), sehingga total kompleksitasnya O(n log k) untuk n elemen. Teknik ini dipakai saat menggabungkan potongan file yang sangat besar.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.