Binary heap adalah binary tree komplet yang disimpan dalam array, dengan properti heap: setiap node lebih kecil (min-heap) atau lebih besar (max-heap) daripada kedua anaknya. Heap memberi akses ke elemen minimum/maksimum dalam O(1) dan operasi push/pop dalam O(log n). Priority queue adalah aplikasi langsung heap: elemen dengan prioritas tertinggi dikeluarkan lebih dulu. Pada chapter ini kita akan mengimplementasikan min-heap dengan array storage, lalu priority queue berbasis max-heap untuk penjadwalan task.

Konsep Binary Heap #

Binary heap adalah binary tree dengan dua properti:

  1. Shape property: tree komplet—semua level penuh kecuali mungkin level terakhir, yang diisi dari kiri ke kanan.
  2. Heap property: min-heap—parent selalu lebih kecil dari kedua anak; max-heap—parent selalu lebih besar.

Properti shape memungkinkan heap disimpan dalam array tanpa pointer. Indeks parent dari node i adalah (i-1)/2. Anak kiri: 2i+1. Anak kanan: 2i+2. Indeks 0 adalah root. Array storage menghemat memori (tidak perlu pointer) dan cache-friendly.

Implementasi Min-Heap #

Operasi dasar heap: push (tambah elemen, sift up) dan pop (ambil root, sift down). Sift up membandingkan elemen baru dengan parent, tukar bila melanggar heap property, ulangi sampai root atau posisi benar. Sift down membandingkan root dengan kedua anak, tukar dengan yang lebih kecil, ulangi sampai leaf.

c 
#include <stdio.h>
#include <stdlib.h>

#define KAPASITAS 64

typedef struct {
    int data[KAPASITAS];
    int ukuran;
} min_heap;

void mh_init(min_heap *h) { h->ukuran = 0; }
int mh_kosong(min_heap *h) { return h->ukuran == 0; }

/* Indeks parent, anak kiri, anak kanan */
static int induk(int i) { return (i - 1) / 2; }
static int kiri(int i) { return 2 * i + 1; }
static int kanan(int i) { return 2 * i + 2; }

static void tukar(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Naikkan elemen ke atas sampai heap property terpenuhi */
static void sift_up(min_heap *h, int i) {
    while (i > 0 && h->data[induk(i)] > h->data[i]) {
        tukar(&h->data[induk(i)], &h->data[i]);
        i = induk(i);
    }
}

/* Turunkan elemen ke bawah sampai heap property terpenuhi */
static void sift_down(min_heap *h, int i) {
    while (1) {
        int terkecil = i;
        int l = kiri(i), r = kanan(i);
        if (l < h->ukuran && h->data[l] < h->data[terkecil]) terkecil = l;
        if (r < h->ukuran && h->data[r] < h->data[terkecil]) terkecil = r;
        if (terkecil == i) break;
        tukar(&h->data[i], &h->data[terkecil]);
        i = terkecil;
    }
}

int mh_push(min_heap *h, int val) {
    if (h->ukuran >= KAPASITAS) return -1;
    h->data[h->ukuran] = val;
    h->ukuran++;
    sift_up(h, h->ukuran - 1);
    return 0;
}

int mh_pop(min_heap *h, int *out) {
    if (mh_kosong(h)) return -1;
    *out = h->data[0];
    h->ukuran--;
    if (h->ukuran > 0) {
        h->data[0] = h->data[h->ukuran];
        sift_down(h, 0);
    }
    return 0;
}

int mh_peek(min_heap *h, int *out) {
    if (mh_kosong(h)) return -1;
    *out = h->data[0];
    return 0;
}

int main(void) {
    min_heap h;
    mh_init(&h);

    int nilai[] = {40, 10, 30, 5, 20, 50, 15};
    int n = sizeof(nilai) / sizeof(nilai[0]);

    printf("Push berurutan:\n");
    for (int i = 0; i < n; i++) {
        mh_push(&h, nilai[i]);
        int top;
        mh_peek(&h, &top);
        printf("  push %d -> top sekarang: %d\n", nilai[i], top);
    }

    printf("\nPop semua (urut menaik - heap sort):\n");
    while (!mh_kosong(&h)) {
        int val;
        mh_pop(&h, &val);
        printf("  pop %d\n", val);
    }

    return 0;
}

Output yang Dihasilkan:

text 
Push berurutan:
  push 40 -> top sekarang: 40
  push 10 -> top sekarang: 10
  push 30 -> top sekarang: 10
  push 5 -> top sekarang: 5
  push 20 -> top sekarang: 5
  push 50 -> top sekarang: 5
  push 15 -> top sekarang: 5

Pop semua (urut menaik - heap sort):
  pop 5
  pop 10
  pop 15
  pop 20
  pop 30
  pop 40
  pop 50

Setelah push 5, top selalu 5 karena 5 adalah minimum. Pop mengeluarkan elemen dari yang terkecil—proses ini disebut heap sort: heap dapat dipakai untuk sorting dengan kompleksitas O(n log n), in-place bila diimplementasikan dengan tepat.

Mari kita telaah baris-baris kode di atas:

  1. Baris 8-11 (min_heap struct): array data dengan kapasitas tetap dan field ukuran. Tidak ada pointer—heap menggunakan indeks array murni.
  2. Baris 13-15 (induk, kiri, kanan): rumus aritmatika untuk navigasi tree dari indeks array. induk(i) = (i-1)/2 (pembagian integer). kiri(i) = 2i+1. kanan(i) = 2i+2.
  3. Baris 22-28 (sift_up): bila parent lebih besar dari current (min-heap dilanggar), tukar, lalu lanjutkan dari posisi parent. Loop sampai root atau heap property terpenuhi. Kompleksitas O(log n).
  4. Baris 31-42 (sift_down): bandingkan current dengan kedua anak, pilih yang terkecil, tukar bila perlu. Lanjutkan dari posisi anak yang ditukar. Kompleksitas O(log n).
  5. Baris 44-51 (mh_push): taruh elemen baru di akhir array (indeks ukuran), increment ukuran, lalu sift_up dari posisi tersebut untuk memperbaiki heap property.
  6. Baris 53-62 (mh_pop): ambil root (elemen minimum), ganti dengan elemen terakhir, decrement ukuran, lalu sift_down dari root untuk memperbaiki heap property.

Priority Queue dengan Max-Heap #

Priority queue adalah struktur data yang mengeluarkan elemen berprioritas tertinggi lebih dulu. Max-heap cocok untuk ini: root selalu elemen dengan prioritas tertinggi. Contoh aplikasi: penjadwalan task OS, algoritma Dijkstra, algoritma Huffman coding.

c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define KAPASITAS 32

typedef struct {
    char nama[32];
    int prioritas;
} task;

typedef struct {
    task data[KAPASITAS];
    int ukuran;
} pq_max;

void pq_init(pq_max *pq) { pq->ukuran = 0; }
int pq_kosong(pq_max *pq) { return pq->ukuran == 0; }

static int induk(int i) { return (i - 1) / 2; }
static int kiri(int i) { return 2 * i + 1; }
static int kanan(int i) { return 2 * i + 2; }

static void tukar(task *a, task *b) { task t = *a; *a = *b; *b = t; }

static void sift_up(pq_max *pq, int i) {
    while (i > 0 && pq->data[induk(i)].prioritas < pq->data[i].prioritas) {
        tukar(&pq->data[induk(i)], &pq->data[i]);
        i = induk(i);
    }
}

static void sift_down(pq_max *pq, int i) {
    while (1) {
        int terbesar = i;
        int l = kiri(i), r = kanan(i);
        if (l < pq->ukuran && pq->data[l].prioritas > pq->data[terbesar].prioritas)
            terbesar = l;
        if (r < pq->ukuran && pq->data[r].prioritas > pq->data[terbesar].prioritas)
            terbesar = r;
        if (terbesar == i) break;
        tukar(&pq->data[i], &pq->data[terbesar]);
        i = terbesar;
    }
}

int pq_push(pq_max *pq, const char *nama, int prioritas) {
    if (pq->ukuran >= KAPASITAS) return -1;
    strncpy(pq->data[pq->ukuran].nama, nama, sizeof(pq->data[0].nama) - 1);
    pq->data[pq->ukuran].nama[sizeof(pq->data[0].nama) - 1] = '\0';
    pq->data[pq->ukuran].prioritas = prioritas;
    pq->ukuran++;
    sift_up(pq, pq->ukuran - 1);
    return 0;
}

int pq_pop(pq_max *pq, task *out) {
    if (pq_kosong(pq)) return -1;
    *out = pq->data[0];
    pq->ukuran--;
    if (pq->ukuran > 0) {
        pq->data[0] = pq->data[pq->ukuran];
        sift_down(pq, 0);
    }
    return 0;
}

int main(void) {
    pq_max pq;
    pq_init(&pq);

    pq_push(&pq, "Backup database", 5);
    pq_push(&pq, "Kirim email urgent", 9);
    pq_push(&pq, "Update dokumen", 3);
    pq_push(&pq, "Restart server", 8);
    pq_push(&pq, "Bersihkan log", 2);

    printf("Eksekusi task sesuai prioritas (max-heap):\n");
    while (!pq_kosong(&pq)) {
        task t;
        pq_pop(&pq, &t);
        printf("  [prio %d] %s\n", t.prioritas, t.nama);
    }

    return 0;
}

Output yang Dihasilkan:

text 
Eksekusi task sesuai prioritas (max-heap):
  [prio 9] Kirim email urgent
  [prio 8] Restart server
  [prio 5] Backup database
  [prio 3] Update dokumen
  [prio 2] Bersihkan log

Task dieksekusi sesuai prioritas: “Kirim email urgent” (prioritas 9) dieksekusi pertama, “Bersihkan log” (prioritas 2) terakhir. Insert dilakukan dengan urutan acak, tetapi pop selalu mengeluarkan prioritas tertinggi.

Kompleksitas Heap #

OperasiKompleksitasCatatan
Peek (lihat root)O(1)Langsung akses data[0]
PushO(log n)Sift up dari leaf ke root
PopO(log n)Sift down dari root ke leaf
Build dari arrayO(n)Sift down dari tengah ke root
Heap sortO(n log n)n kali pop
Ruang tambahanO(1)In-place (array storage)

Aplikasi Heap di Standard Library #

Fungsi standar C tidak menyediakan heap langsung, tetapi qsort() bisa dipakai untuk sorting satu kali. Untuk priority queue dinamis (push/pop berulang), implementasi manual seperti di atas adalah pilihan praktis. Beberapa library pihak ketiga seperti glib menyediakan GQueue dengan operasi priority.