Binary heap: priority queue, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan heap

Banyak program berulang kali membutuhkan item paling mendesak dari kumpulan yang terus berubah: event berikutnya dalam simulasi, node terdekat yang belum dikunjungi pada algoritma Dijkstra, tugas dengan prioritas tertinggi, atau k nilai terbesar dalam sebuah stream. Mengurutkan seluruh kumpulan setiap kali insert butuh O(n log n) setiap kali. Sorted list membuat penghapusan murah tetapi insert O(n). Heap membuat insert dan remove-min sama-sama O(log n), persis yang dibutuhkan priority queue.

Ide dasarnya: tree yang disimpan dalam array

Heap adalah complete binary tree: setiap level penuh kecuali mungkin yang terakhir, yang diisi dari kiri. Bentuk itu memungkinkan kita menyimpan tree dalam list biasa tanpa pointer.

Dua operasi perbaikan menjaga heap property. Sift up: setelah menambahkan item baru di akhir, tukar dengan induknya selama ia lebih kecil. Sift down: setelah memindahkan item terakhir ke root, tukar dengan anak yang lebih kecil selama ia lebih besar dari anak itu. Setiap operasi bergerak di satu jalur root-ke-leaf, jadi paling banyak sekitar log2(n) pertukaran.

Contoh langkah demi langkah: push dan pop

Mulai dari min-heap [2, 5, 3, 9, 6] (2 adalah root, anak-anaknya 5 dan 3, dan 5 punya anak 9 dan 6).

1. Push 1: tambahkan di akhir, menjadi [2, 5, 3, 9, 6, 1]. Indeks 5 punya induk di indeks 2 (nilai 3).
2. 1 lebih kecil dari 3, tukar: [2, 5, 1, 9, 6, 3]. Sekarang indeks 2 punya induk di indeks 0 (nilai 2).
3. 1 lebih kecil dari 2, tukar: [1, 5, 2, 9, 6, 3]. Sudah sampai root, berhenti.
4. Pop: hapus root 1, pindahkan item terakhir 3 ke root: [3, 5, 2, 9, 6].
5. Anak root adalah 5 dan 2; yang lebih kecil adalah 2, dan 3 lebih besar, tukar: [2, 5, 3, 9, 6]. Indeks 2 tidak punya anak, berhenti. Pop mengembalikan 1.

Implementasi min-heap di Python

Kelas ini menunjukkan mekanismenya. Di kode sebenarnya gunakan heapq, seperti pada bagian berikutnya.

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

Priority queue dengan heapq Python

Modul heapq bekerja pada list biasa dan selalu menjaganya sebagai min-heap. heapify mengubah list yang sudah ada menjadi heap di tempat dalam O(n). Untuk memakai prioritas, push tuple: Python membandingkan tuple elemen demi elemen, jadi elemen pertama adalah prioritasnya. Tambahkan counter sebagai tie-breaker agar item dengan prioritas sama tidak perlu dibandingkan langsung.

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

Untuk max-heap, Python 3.14 menambahkan heapq.heapify_max, heapq.heappush_max, dan heapq.heappop_max. Pada versi lama, triknya adalah mem-push key yang dinegasikan, misalnya heapq.heappush(h, -score), lalu menegasikannya lagi saat pop.

Kompleksitas waktu dan ruang

Membangun heap dengan memanggil push sebanyak n kali butuh O(n log n). heapify melakukan sift down dari induk terakhir sampai root dan butuh O(n), jadi pilih itu jika semua item sudah ada.

Varian dan kesalahan umum

• Max-heap: kode yang sama dengan perbandingan dibalik; di Python, pakai fungsi _max (3.14 ke atas) atau negasikan key.
• d-ary heap: setiap node punya d anak. Tree yang lebih dangkal membuat push lebih murah dan pop sedikit lebih mahal.
• Indexed priority queue / decrease-key: heapq tidak bisa mengubah prioritas item di tempat. Solusi umumnya (dipakai pada algoritma Dijkstra) adalah mem-push entri baru dan melewati entri usang saat di-pop.
• Membandingkan item yang tidak bisa dibandingkan: mem-push (priority, dict) memunculkan TypeError ketika dua prioritas sama, karena Python lalu membandingkan dict-nya. Tambahkan counter sebagai elemen kedua tuple.
• Menganggap list heap itu terurut. Hanya heap[0] yang dijamin; gunakan sorted(heap) jika Anda butuh semuanya berurutan.
• Kesalahan off-by-one saat mencampur rumus berbasis 1 dari buku teks (anak 2i dan 2i + 1) dengan list Python berbasis 0.

Kapan memakai heap dan soal-soal khasnya

Gunakan heap ketika Anda berulang kali hanya butuh item terkecil atau terbesar dari kumpulan yang terus berubah. Gunakan sorted list atau balanced tree jika Anda juga butuh iterasi terurut atau penghapusan sembarang, dan min() biasa jika Anda hanya butuh minimum satu kali.

Penggunaan klasik: shortest path Dijkstra dan minimum spanning tree Prim, menggabungkan k sorted list (heapq.merge), mencari k item terbesar atau terkecil (pertahankan heap berukuran k, O(n log k)), median berjalan (dua heap), task scheduler dan simulasi berbasis event, serta heapsort.