Penjelasan heapsort: cara kerja, kode, dan kompleksitas

Ide dasar dengan kata-kata sederhana

Heapsort adalah selection sort dengan cara yang lebih cepat untuk mencari nilai maksimum. Selection sort memindai seluruh bagian belum terurut, O(n) setiap kali. Heapsort menyimpan bagian belum terurut sebagai heap, sehingga nilai maksimum selalu ada di indeks 0 dan memulihkan urutan setelah mengambilnya hanya berbiaya O(log n).

Binary heap disimpan dalam array biasa tanpa pointer. Untuk elemen di indeks i:

• anak kiri ada di 2*i + 1 dan anak kanan di 2*i + 2;
• parent ada di (i - 1) // 2;
• pada max-heap, setiap parent lebih besar atau sama dengan anak-anaknya, sehingga elemen terbesar ada di indeks 0.

1. Bangun max-heap dari array dengan men-sift down setiap node non-daun, mulai dari yang terakhir dan bergerak ke indeks 0.
2. Tukar root (nilai maksimum) dengan elemen terakhir heap. Elemen itu kini berada di tempat akhirnya.
3. Kecilkan heap satu elemen dan sift root baru ke bawah sampai sifat heap berlaku lagi.
4. Ulangi langkah 2 dan 3 sampai heap tinggal satu elemen.

Contoh langkah demi langkah

Urutkan [4, 10, 3, 5, 1]. Elemen setelah garis sudah terurut dan final.

Implementasi Python

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

Modul heapq Python menyediakan min-heap pada list biasa. Mengeluarkan setiap elemen menghasilkan list terurut, yang merupakan heapsort singkat (tidak in-place):

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

Kompleksitas waktu dan ruang

Membangun heap secara bottom-up adalah O(n), bukan O(n log n), karena jumlah tinggi node pada complete binary tree adalah O(n). Fase ekstraksi yang mendominasi total.

Perbandingan heapsort dengan sort lain

Heapsort tidak stabil: menukar root ke akhir dapat membawa elemen melewati elemen lain yang berkunci sama. Kekuatan utamanya adalah kasus terburuk O(n log n) yang terjamin bersama ruang tambahan O(1), kombinasi yang tidak ditawarkan quicksort maupun merge sort. Kelemahannya ada pada akses memori: melompat antara indeks i dan 2*i + 1 kurang memanfaatkan cache CPU, sehingga biasanya lebih lambat daripada quicksort yang diimplementasikan dengan baik. Introsort memakai heapsort sebagai cadangan ketika quicksort berekursi terlalu dalam.

Varian dan kesalahan umum

• Pengurutan parsial: untuk mendapatkan hanya k item terbesar, bangun heap lalu ekstrak k kali, O(n + k log n). Di Python, heapq.nlargest dan heapq.nsmallest melakukannya.
• Top-k dari aliran data (stream): pertahankan min-heap berukuran k dan push atau ganti setiap item baru, waktu O(n log k) dan memori O(k).
• Bottom-up heapsort men-sift lubang ke bawah sampai daun terlebih dahulu lalu naik, yang menghemat perbandingan.
• Smoothsort, varian berbasis heap buatan Dijkstra, berjalan dalam O(n) pada input yang sudah terurut tetapi jarang dipakai karena rumit.

Kapan memakai heapsort

Pakai heapsort ketika Anda butuh kasus terburuk O(n log n) yang terjamin tanpa memori tambahan, misalnya pada sistem embedded atau real-time, atau sebagai cadangan pengaman di dalam sort lain. Untuk kode Python sehari-hari, pakai sorted(), yang stabil dan lebih cepat pada data umum. Heap itu sendiri lebih berguna daripada pengurutannya: priority queue, jalur terpendek Dijkstra, scheduler, penggabungan k list terurut (heapq.merge), dan pencarian k nilai terbesar semuanya dibangun di atasnya. Wawancara sering menanyakan rumus indeks heap, mengapa membangun heap itu O(n), dan masalah top-k.