TeachingAlgorithm Design and AnalysisSesi 6 — Data Structures: Graph, Priority Queue & Heap
Week 3Workshop

Sesi 6 — Data Structures: Graph, Priority Queue & Heap

Sesi 6 — Data Structures: Graph, Priority Queue & Heap (incl. Space Complexity)

COMP6049001 — Algorithm Design and Analysis

Daftar Isi

  1. Konsep Graph
  2. Representasi Graph
  3. Analisis Kompleksitas Representasi Graph
  4. Graph Traversal: BFS dan DFS
  5. Priority Queue
  6. Heap
  7. Heapsort
  8. Ringkasan Perbandingan Space Complexity
  9. Latihan Soal & Pembahasan

Kaitan dengan Sesi Sebelumnya

Sesi ini melanjutkan langsung dari Sesi 5 — dari struktur data linear dan hierarkis ke struktur yang lebih umum:

Konsep dari sesi sebelumnya Diterapkan di Sesi 6 sebagai
Stack (Sesi 5) Struktur pendukung DFS
Queue (Sesi 5) Struktur pendukung BFS
Tree sebagai graph connected+acyclic (Sesi 5) Graph = generalisasi tree tanpa batasan acyclic
Complete binary tree (Sesi 5) Struktur dasar Heap
Auxiliary space (Sesi 5) Trade-off matrix O(V²) vs. list O(V+E)
Notasi O, Ω, Θ (Sesi 4) Analisis semua operasi heap dan graph
Worst vs. average case (Sesi 3) BUILD-MAX-HEAP: analisis longgar O(n log n) vs. ketat O(n)

1. Konsep Graph

1.1 Definisi Informal

Graph adalah struktur data abstrak untuk merepresentasikan konsep graf matematis — yaitu kumpulan vertex (node) dan edge yang menghubungkan vertex-vertex tersebut.

Hubungan dengan tree (Sesi 5): graph adalah generalisasi dari tree. Kalau tree hanya mengizinkan hubungan parent-to-child yang hierarkis dan tidak boleh ada siklus, graph mengizinkan hubungan kompleks apapun antar node — termasuk siklus, node yang saling menunjuk, atau bahkan node yang terisolasi.

Tree (Sesi 5) Graph (Sesi 6)
Connected? Harus Tidak harus
Acyclic? Harus Boleh ada cycle
Root? Ada, ditetapkan Tidak ada konsep root
Jumlah edge Tepat n − 1 Bebas, dari 0 sampai n(n−1)/2

1.2 Definisi Formal

Graph G didefinisikan sebagai pasangan terurut (V, E), dengan:

  • V(G) = himpunan vertex
  • E(G) = himpunan edge yang menghubungkan vertex-vertex tersebut

1.3 Directed vs. Undirected

Jenis Sifat edge Notasi
Undirected Edge tidak punya arah — (A,B) sama dengan (B,A) Pasangan tak terurut
Directed Edge punya arah — (A,B) berbeda dari (B,A) Pasangan terurut

Contoh Undirected Graph:

    A ---- B
    |    / |
    |   /  |
    |  /   |
    D ---- E ---- C

V(G) = {A, B, C, D, E} E(G) = {(A,B), (A,D), (B,C), (B,D), (C,E), (D,E)}

Contoh Directed Graph:

    A ---→ B
    |      ↓
    ↓      |
    D ←----+
    |
    ↓
    E ---→ C ---→ B

V(G) = {A, B, C, D, E} E(G) = {(A,B), (A,D), (B,D), (C,B), (D,E), (E,C)}

Pada directed graph, urutan dalam pasangan menentukan arah: (A,B) berarti "ada edge dari A ke B", tapi belum tentu ada edge dari B ke A.

1.4 Istilah Tambahan yang Perlu Diketahui

Istilah Arti
Adjacent Dua vertex disebut adjacent (bertetangga) jika ada edge yang menghubungkan keduanya
Degree — deg(u) Jumlah edge yang terhubung ke vertex u
Weighted graph Setiap edge punya bobot/nilai (misalnya jarak, biaya, kapasitas)
Simple graph Graph tanpa self-loop (edge dari suatu node ke dirinya sendiri) dan tanpa edge ganda
Sparse graph Jumlah edge sedikit relatif terhadap vertex — E = O(V)
Dense graph Jumlah edge banyak, mendekati maksimum — E ≈ V²

2. Representasi Graph

Ada dua cara umum menyimpan graph di memori komputer:

  1. Adjacency Matrix — representasi sekuensial (pakai array 2D)
  2. Adjacency List — representasi berbasis linked list

2.1 Adjacency Matrix

Adjacency matrix adalah matriks V×V yang menyatakan node mana bertetangga dengan node mana.

Aturan pengisian:

$$A[i][j] = \begin{cases} 1 & \text{jika ada edge dari } i \text{ ke } j \ 0 & \text{jika tidak ada edge} \end{cases}$$

Untuk weighted graph, nilai 1 diganti dengan bobot edge-nya.

Contoh — Undirected Graph

Graph:

    A ---- B
    |      |
    |      |
    D ---- C

Adjacency matrix:

A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0

Empat Kesimpulan Penting dari Adjacency Matrix

  1. Simple graph (tanpa self-loop) → diagonal selalu 0. Karena A[i][i] = 1 berarti ada edge dari i ke dirinya sendiri, yang tidak diperbolehkan pada simple graph.

  2. Undirected graph → matriksnya simetris. Karena kalau ada edge (A,B), otomatis juga berarti ada edge (B,A). Jadi A[i][j] = A[j][i] selalu.

  3. Jumlah entri non-zero = jumlah edge. Untuk directed graph: jumlah 1 = jumlah edge. Untuk undirected graph: jumlah 1 = 2 × jumlah edge (karena tiap edge dihitung dua kali, di A[i][j] dan A[j][i]).

  4. Weighted graph → matriksnya berisi bobot, bukan cuma 0/1.

2.2 Adjacency List

Adjacency list terdiri dari daftar semua node di G. Setiap node kemudian ditautkan ke list-nya sendiri yang berisi nama-nama semua node yang bertetangga dengannya.

Contoh — Undirected Graph (graph yang sama seperti di atas)

A → [B, D]
B → [A, C]
C → [B, D]
D → [A, C]

Contoh — Weighted Directed Graph

A → [(B, 5), (D, 3)]
B → [(C, 2)]
C → [(A, 7)]
D → [(C, 1)]

Setiap entri menyimpan pasangan (tetangga, bobot).

Keunggulan Adjacency List

Keunggulan Penjelasan
Mudah dibaca Langsung terlihat siapa saja tetangga suatu node
Efisien untuk sparse graph Hanya menyimpan edge yang benar-benar ada, tidak ada slot kosong
Mudah menambah node baru Tinggal tambah entri baru di list

Kontras dengan matrix: menambah node pada adjacency matrix itu sulit — ukuran matriks harus diubah (dari V×V menjadi (V+1)×(V+1)), dan node yang sudah ada mungkin perlu ditata ulang. Ini operasi mahal yang melibatkan realokasi seluruh matriks.

Pedoman umum:

  • Sparse graph (sedikit edge) → adjacency list
  • Dense graph (banyak edge) → adjacency matrix

3. Analisis Kompleksitas Representasi Graph

3.1 Tabel Perbandingan

Representasi Space Edge check (cek apakah ada edge u-v) Iterate neighbors (telusuri tetangga u)
Adjacency matrix O(V²) O(1) O(V)
Adjacency list O(V + E) O(deg(u)) O(deg(u))

3.2 Penjelasan Setiap Entri

Space: O(V²) vs. O(V + E)

Matrix — O(V²): matriks V×V selalu butuh V² sel, terlepas dari berapa banyak edge yang sebenarnya ada. Graph dengan 1000 vertex dan hanya 5 edge tetap butuh 1.000.000 sel, yang hampir semuanya berisi 0.

List — O(V + E): butuh V entri untuk daftar node, ditambah total E entri (atau 2E untuk undirected) untuk menyimpan tetangga. Ruang yang dipakai sebanding dengan jumlah edge yang benar-benar ada.

Edge Check: O(1) vs. O(deg(u))

Matrix — O(1): untuk mengecek apakah ada edge antara u dan v, cukup baca A[u][v] — satu akses array langsung.

List — O(deg(u)): harus menelusuri seluruh list tetangga u untuk mencari apakah v ada di sana. Kalau u punya banyak tetangga, ini lambat.

Iterate Neighbors: O(V) vs. O(deg(u))

Matrix — O(V): untuk mencari semua tetangga u, harus memeriksa seluruh baris A[u][0..V−1], termasuk sel-sel yang berisi 0. Jadi selalu V langkah, walaupun u cuma punya 2 tetangga.

List — O(deg(u)): cukup telusuri list tetangga u, yang panjangnya persis deg(u). Tidak ada waktu terbuang untuk memeriksa non-tetangga.

3.3 Trade-off Kunci: Sparse Graph

Untuk sparse graph (E = O(V)), adjacency list memakai O(V) space vs. O(V²) untuk matrix — peningkatan sebesar faktor V.

Verifikasi numerik — graph dengan V = 1.000 vertex dan E = 2.000 edge (sparse):

Representasi Perhitungan Total sel/entri
Adjacency matrix V² = 1.000² 1.000.000
Adjacency list V + 2E = 1.000 + 4.000 5.000

Adjacency list 200× lebih hemat untuk kasus ini. Sebaliknya, untuk dense graph dengan E ≈ V²/2, keduanya menjadi sebanding, dan matrix menang karena edge check-nya O(1).

3.4 Cara Memilih Representasi

Situasi Pilihan
Graph sparse, memori terbatas Adjacency list
Graph dense Adjacency matrix
Sering melakukan edge check Adjacency matrix (O(1))
Sering iterasi tetangga (misal BFS/DFS) Adjacency list (O(deg) bukan O(V))
Sering menambah vertex baru Adjacency list

4. Graph Traversal: BFS dan DFS

4.1 Konsep Umum

Traversal adalah metode memeriksa node dan edge di dalam graph secara sistematis. Ada dua metode standar:

Metode Struktur data pendukung Pola gerak
BFS (Breadth-First Search) Queue (FIFO) Melebar per level
DFS (Depth-First Search) Stack (LIFO) Mendalam per cabang

Ini penerapan langsung dari Stack dan Queue yang dipelajari di Sesi 5 — pilihan struktur data inilah yang menentukan urutan kunjungan.

4.2 Variabel STATUS

Kedua algoritma memakai variabel status untuk melacak kondisi setiap node:

Status Nama state Keterangan
1 Ready Kondisi awal — node belum tersentuh
2 Waiting Node sudah dimasukkan ke queue/stack, menunggu diproses
3 Processed Node sudah selesai diproses

Kenapa perlu tiga status, bukan cuma "sudah/belum dikunjungi"? Karena ada kondisi antara: node yang sudah masuk antrean tapi belum diproses. Tanpa membedakan ini, node bisa masuk queue/stack berkali-kali (jika beberapa tetangganya sama-sama menunjuk ke node itu), yang menyebabkan pemrosesan berulang dan bahkan infinite loop pada graph bersiklus.

4.3 BFS — Breadth-First Search

BFS dimulai dari root node dan mengeksplorasi semua node tetangganya terlebih dulu. Kemudian untuk setiap node terdekat itu, algoritma mengeksplorasi tetangga mereka yang belum dieksplorasi, dan seterusnya.

Algoritma BFS

Step 1: SET STATUS = 1 (ready state) untuk setiap node di G
Step 2: Enqueue node awal A dan set STATUS = 2 (waiting state)
Step 3: Ulangi Step 4 dan 5 sampai QUEUE kosong
Step 4:     Dequeue node N. Proses N, set STATUS = 3 (processed state)
Step 5:     Enqueue semua tetangga N yang berstatus ready (STATUS = 1)
            dan set STATUS mereka = 2 (waiting state)
        [END OF LOOP]
Step 6: EXIT

Contoh Penelusuran BFS

Graph contoh (dari slide, dengan node A–I), dimulai dari A:

Iterasi Node diproses Queue setelahnya Node baru jadi waiting
— (inisialisasi) [A] A
1 A [B, C, D] B, C, D
2 B [C, D, E] E
3 C [D, E, G] G
4 D [E, G] —
5 E [G, F] F
6 G [F, H, I] H, I
7 F [H, I] —
8 H [I] —
9 I [] —

Urutan hasil BFS: A, B, C, D, E, G, F, H, I

Pola yang terlihat: A diproses dulu (level 0), lalu semua tetangga langsungnya B, C, D (level 1), baru tetangga dari mereka (level 2), dan seterusnya. Inilah yang dimaksud "melebar per level".

4.4 DFS — Depth-First Search

Algoritma DFS

Step 1: SET STATUS = 1 (ready state) untuk setiap node di G
Step 2: Push node awal A ke stack dan set STATUS = 2 (waiting state)
Step 3: Ulangi Step 4 dan 5 sampai STACK kosong
Step 4:     Pop node teratas N. Proses N, set STATUS = 3 (processed state)
Step 5:     Push ke stack semua tetangga N yang berstatus ready (STATUS = 1)
            dan set STATUS mereka = 2 (waiting state)
        [END OF LOOP]
Step 6: EXIT

Perhatikan: struktur algoritmanya identik dengan BFS — satu-satunya perbedaan adalah queue diganti stack (dan enqueue/dequeue diganti push/pop). Perbedaan sederhana ini sepenuhnya mengubah urutan penelusuran.

Contoh Penelusuran DFS

Graph yang sama, tapi dimulai dari H:

Iterasi Node diproses Stack setelahnya (top di kiri)
— (inisialisasi) [H]
1 H [E, I]
2 I [E, F]
3 F [E, C]
4 C [E, B, G]
5 G [E, B]
6 B [E]
7 E []

Urutan hasil DFS: H, I, F, C, G, B, E

Observasi Penting: Node Tak Terjangkau

Perhatikan bahwa node A dan D tidak tersentuh sama sekali. Ini bukan bug — artinya A dan D tidak reachable dari H pada graph berarah ini.

Implikasi praktis: BFS/DFS hanya menjelajahi komponen terhubung yang memuat node awal. Untuk menjelajahi seluruh graph yang mungkin terdiri dari beberapa komponen terpisah, algoritma harus dijalankan berulang dari setiap node yang belum tersentuh. Sifat ini justru berguna — DFS/BFS dapat dipakai untuk mendeteksi apakah graph terhubung atau untuk menghitung jumlah komponen terhubung.

4.5 Kompleksitas BFS dan DFS

$$\text{Time} = O(V + E), \quad \text{Auxiliary Space} = O(V)$$

Penjelasan time O(V + E):

  • Setiap vertex masuk dan keluar queue/stack tepat sekali → O(V)
  • Setiap edge diperiksa tepat sekali (atau dua kali untuk undirected) → O(E)
  • Total: O(V) + O(E) = O(V + E)

Penjelasan space O(V):

  • Array status untuk V node → O(V)
  • Queue/stack yang di worst case bisa berisi hingga V node → O(V)
  • Total: O(V)

Catatan: kompleksitas O(V + E) ini berlaku jika graph direpresentasikan dengan adjacency list. Dengan adjacency matrix, mencari tetangga setiap node butuh O(V), sehingga total menjadi O(V²) — ini salah satu alasan penting mengapa adjacency list lebih disukai untuk algoritma traversal.

4.6 Perbandingan BFS vs. DFS

BFS DFS
Struktur pendukung Queue Stack
Pola Melebar per level Mendalam per cabang
Shortest path (unweighted)? Ya Tidak
Aplikasi khas Shortest path, level/jarak dari titik awal, web crawling Deteksi cycle, topological sort, connected components, backtracking
Space worst case O(V) — bisa banyak node di satu level O(V) — bisa sedalam V

5. Priority Queue

5.1 Definisi

Priority Queue adalah pengembangan lebih lanjut dari konsep Queue, di mana setiap komponen terdiri dari pasangan (key, value).

Perbedaan mendasar dengan Queue biasa:

Queue biasa (Sesi 5) Priority Queue
Urutan keluar FIFO — sesuai urutan masuk Berdasarkan prioritas (key), bukan urutan masuk
Operasi ekstraksi Ambil yang paling depan Ambil yang prioritas tertinggi (max) atau terendah (min)

Analogi: antrean di rumah sakit. Queue biasa = layani sesuai urutan datang. Priority queue = pasien gawat darurat dilayani lebih dulu, terlepas kapan datangnya.

5.2 Aplikasi Priority Queue

Aplikasi Cara pakai
Job scheduling Selalu proses task dengan prioritas tertinggi berikutnya
Algoritma Dijkstra (Sesi 20) Selalu relaksasi vertex terdekat yang belum dikunjungi
Prim's MST (Sesi 11) Selalu tambahkan edge dengan bobot minimum ke tree
Huffman coding (Sesi 12) Selalu gabungkan dua tree dengan frekuensi terendah
Event simulation Selalu proses event yang paling awal waktunya
Antrean penumpang standby pesawat Prioritas berdasarkan status keanggotaan/harga tiket
Stock market Order dengan harga terbaik diproses lebih dulu

Perhatikan pola yang sama di semua aplikasi ini: "selalu ambil yang paling ekstrem (max/min) berikutnya". Inilah fungsi inti priority queue, dan mengapa struktur ini muncul berulang kali di algoritma greedy (Sesi 11-12) dan graph (Sesi 20).

5.3 Implementasi Priority Queue

Priority queue adalah konsep abstrak (ADT — Abstract Data Type) yang bisa diimplementasikan dengan berbagai struktur:

Implementasi Insert Extract-Max Peek-Max
Array tak terurut O(1) O(n) — harus scan semua O(n)
Array terurut O(n) — harus geser elemen O(1) O(1)
Heap O(log n) O(log n) O(1)

Kenapa Heap yang dipilih? Karena memberi keseimbangan terbaik: array tak terurut cepat untuk insert tapi lambat untuk extract; array terurut sebaliknya. Heap mengorbankan sedikit di kedua sisi (O(log n) di keduanya, bukan O(1)) tapi tidak pernah O(n) di operasi manapun. Untuk aplikasi yang sering melakukan keduanya (seperti Dijkstra), ini jauh lebih baik.

6. Heap

6.1 Definisi

Sebuah (max-)heap adalah nearly complete binary tree yang disimpan sebagai array A[1..n], memenuhi max-heap property: $$A[\text{PARENT}(i)] \geq A[i] \quad \text{untuk semua } i > 1$$

Artinya: key setiap node ≥ key anak-anaknya. Konsekuensinya, elemen maksimum selalu berada di A[1] (root).

Dua jenis heap:

Jenis Property Elemen di root
Max-Heap Parent ≥ children Nilai terbesar
Min-Heap Parent ≤ children Nilai terkecil

Dua syarat yang harus dipenuhi sekaligus:

  1. Struktur: complete binary tree (semua level terisi penuh kecuali level terakhir, yang terisi dari kiri) — konsep dari Sesi 5
  2. Order: memenuhi max-heap atau min-heap property

6.2 Representasi Array

Heap tidak disimpan dengan pointer seperti BST, melainkan sebagai array biasa. Relasi parent-child dihitung dari indeksnya:

$$\text{PARENT}(i) = \lfloor i/2 \rfloor, \quad \text{LEFT}(i) = 2i, \quad \text{RIGHT}(i) = 2i+1$$

(Menggunakan indeks berbasis-1 seperti CLRS. Untuk indeks berbasis-0 seperti di Python/Java, rumusnya menjadi PARENT(i) = ⌊(i−1)/2⌋, LEFT(i) = 2i+1, RIGHT(i) = 2i+2.)

Contoh

Array: A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

Tree yang direpresentasikan:

              16
            /    \
          14      10
         /  \    /  \
        8    7  9    3
       / \  /
      2   4 1

Verifikasi rumus indeks:

i A[i] LEFT(i)=2i A[LEFT] RIGHT(i)=2i+1 A[RIGHT] Max-heap OK?
1 16 2 14 3 10 16 ≥ 14, 16 ≥ 10 ✓
2 14 4 8 5 7 14 ≥ 8, 14 ≥ 7 ✓
3 10 6 9 7 3 10 ≥ 9, 10 ≥ 3 ✓
4 8 8 2 9 4 8 ≥ 2, 8 ≥ 4 ✓
5 7 10 1 11 — 7 ≥ 1 ✓

Keunggulan representasi array ini:

  • Tidak perlu pointer — hemat memori dibanding BST yang butuh 2 pointer per node
  • Cache-friendly — data tersimpan berurutan di memori, akses lebih cepat di praktik
  • Navigasi O(1) — pindah ke parent/child cuma perlu satu operasi aritmatika

6.3 MAX-HEAPIFY

Memperbaiki max-heap property di node i, dengan asumsi kedua subtree-nya sudah merupakan heap yang valid.

MAX-HEAPIFY(A, i, n)
1   l = LEFT(i), r = RIGHT(i)
2   if l ≤ n and A[l] > A[i]:  largest = l
3   else:                       largest = i
4   if r ≤ n and A[r] > A[largest]:  largest = r
5   if largest ≠ i
6       swap A[i] and A[largest]
7       MAX-HEAPIFY(A, largest, n)

Cara kerja: bandingkan node i dengan kedua anaknya. Jika ada anak yang lebih besar, tukar posisi, lalu rekursif perbaiki di posisi baru tersebut (karena pertukaran bisa merusak property di subtree bawah). Proses ini disebut sift-down (menenggelamkan elemen kecil ke bawah).

Contoh Trace

Misal A = [4, 14, 10, 8, 7] dengan n=5, panggil MAX-HEAPIFY(A, 1, 5):

Awal:         4               Langkah 1: bandingkan 4 dengan anak (14, 10)
            /   \                        largest = 14 (indeks 2)
          14     10                      tukar A[1] ↔ A[2]
         /  \
        8    7

Setelah tukar:  14            Langkah 2: rekursif di indeks 2
              /   \                      bandingkan 4 dengan anak (8, 7)
             4     10                    largest = 8 (indeks 4)
            / \                          tukar A[2] ↔ A[4]
           8   7

Hasil akhir:    14            Langkah 3: rekursif di indeks 4
              /   \                      indeks 4 tidak punya anak → selesai
             8     10
            / \
           4   7

Kompleksitas: O(log n) — karena rekursi turun maksimal sedalam tinggi tree, yaitu h = ⌊log₂ n⌋.

6.4 BUILD-MAX-HEAP

Mengubah array sembarang menjadi max-heap.

BUILD-MAX-HEAP(A, n)
1   for i = ⌊n/2⌋ downto 1
2       MAX-HEAPIFY(A, i, n)

Kenapa mulai dari ⌊n/2⌋, bukan dari n? Karena node dengan indeks lebih besar dari ⌊n/2⌋ adalah leaf — mereka tidak punya anak, sehingga otomatis sudah memenuhi heap property (secara trivial). Tidak perlu di-heapify.

Kenapa dari belakang ke depan (downto)? Karena MAX-HEAPIFY mensyaratkan kedua subtree sudah valid. Dengan memproses dari bawah ke atas, saat kita memanggil MAX-HEAPIFY(i), subtree di bawah i sudah dipastikan valid.

Analisis Kompleksitas: O(n), Bukan O(n log n)

Ini salah satu analisis paling menarik di materi ini.

Analisis longgar (naif): ada O(n) pemanggilan MAX-HEAPIFY, masing-masing O(log n), jadi total O(n log n). Benar, tapi tidak ketat — ini persis kasus "upper bound yang tidak tight" yang dibahas di Sesi 4.

Analisis ketat: kuncinya adalah menyadari bahwa tidak semua node butuh O(log n). Node yang dekat leaf punya subtree pendek, sehingga heapify-nya cepat. Dan sebagian besar node memang berada dekat leaf.

Untuk heap dengan n node, jumlah node pada ketinggian h adalah maksimal ⌈n/2^(h+1)⌉, dan biaya heapify di ketinggian h adalah O(h). Maka total:

$$\sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot O(h) = O\left(n \sum_{h=0}^{\infty} \frac{h}{2^h}\right) = O(n \cdot 2) = O(n)$$

Deret $\sum_{h=0}^{\infty} h/2^h$ konvergen ke 2 — inilah kunci kenapa hasilnya linear, bukan n log n.

Verifikasi intuisi: untuk heap dengan n = 1000 node:

Ketinggian h Jumlah node (≈) Biaya per node Total
0 (leaf) 500 0 0
1 250 1 250
2 125 2 250
3 62 3 186
... ... ... ...
9 (root) 1 9 9

Total ≈ 1.000 — sebanding dengan n, bukan n log n ≈ 10.000. Node-node "mahal" (dekat root) jumlahnya sangat sedikit.

Kompleksitas: O(n)

6.5 HEAP-EXTRACT-MAX

Mengambil dan menghapus elemen terbesar dari heap.

HEAP-EXTRACT-MAX(A, n)
1   if n < 1: error "heap underflow"
2   max = A[1]
3   A[1] = A[n]
4   n = n - 1
5   MAX-HEAPIFY(A, 1, n)
6   return max

Cara kerja:

  1. Simpan A[1] (elemen maksimum) sebagai nilai yang akan dikembalikan
  2. Pindahkan elemen terakhir ke posisi root (A[1])
  3. Kurangi ukuran heap
  4. Panggil MAX-HEAPIFY di root untuk memperbaiki property yang kemungkinan rusak

Kenapa elemen terakhir yang dipindah ke root? Karena untuk mempertahankan bentuk complete binary tree, node yang harus dihapus adalah yang paling kanan di level terbawah — yaitu A[n].

Kompleksitas: O(log n) — didominasi oleh MAX-HEAPIFY.

6.6 MAX-HEAP-INSERT dan HEAP-INCREASE-KEY

MAX-HEAP-INSERT(A, key, n)
1   n = n + 1
2   A[n] = -∞
3   HEAP-INCREASE-KEY(A, n, key)

HEAP-INCREASE-KEY(A, i, key)
1   if key < A[i]: error "new key is smaller"
2   A[i] = key
3   while i > 1 and A[PARENT(i)] < A[i]
4       swap A[i] and A[PARENT(i)]
5       i = PARENT(i)

Cara kerja INSERT: tambahkan slot baru di ujung array dengan nilai −∞ (pasti memenuhi heap property karena lebih kecil dari apapun), lalu naikkan nilainya ke key yang sebenarnya menggunakan HEAP-INCREASE-KEY.

Cara kerja INCREASE-KEY: setelah key dinaikkan, node itu mungkin sekarang lebih besar dari parent-nya. Maka lakukan sift-up (bubble up) — tukar dengan parent berulang kali sampai parent-nya lebih besar atau sudah mencapai root.

Kompleksitas: O(log n) — sift-up naik maksimal sedalam tinggi tree.

6.7 MIN-HEAP-DECREASE-KEY

Untuk algoritma seperti Dijkstra dan Prim, operasi kritisnya adalah DECREASE-KEY pada min-heap: mengurangi key suatu elemen lalu memperbaiki heap property.

MIN-HEAP-DECREASE-KEY(A, i, key)
1   if key > A[i]: error "new key is larger than current key"
2   A[i] = key
3   // Sift up: naikkan key yang dikurangi menuju root
4   while i > 1 and A[PARENT(i)] > A[i]
5       swap A[i] and A[PARENT(i)]
6       i = PARENT(i)

Kenapa Sift UP, Bukan Sift DOWN?

Ini pertanyaan yang penting dipahami logikanya:

Ketika key suatu node dikurangi (jadi lebih kecil) pada min-heap:

  • Terhadap anak-anaknya: tidak ada masalah. Min-heap butuh parent ≤ children. Karena parent jadi lebih kecil, kondisi ini justru makin terpenuhi.
  • Terhadap parent-nya: bisa bermasalah. Parent mungkin sekarang lebih besar dari node ini, melanggar min-heap property.

Karena pelanggaran hanya mungkin terjadi ke atas, kita bubble up sampai parent-nya ≤ key baru.

Peran dalam Algoritma Dijkstra

Saat operasi RELAX(u, v, w) menemukan jalur yang lebih pendek ke v, ia memanggil DECREASE-KEY(Q, v, d[v]) untuk memperbarui prioritas v di min-priority queue.

Inilah alasan Dijkstra membutuhkan O(E log V) dengan binary heap: setiap dari E relaksasi bisa memicu DECREASE-KEY yang biayanya O(log V).

Kompleksitas: O(log n)

6.8 Ringkasan Kompleksitas Operasi Heap

Operasi Time Keterangan
MAX-HEAPIFY O(log n) Sift-down sedalam tinggi tree
BUILD-MAX-HEAP O(n) Analisis ketat — bukan O(n log n)
HEAP-EXTRACT-MAX O(log n) Didominasi heapify
MAX-HEAP-INSERT O(log n) Sift-up sedalam tinggi tree
HEAP-INCREASE-KEY O(log n) Sift-up
MIN-HEAP-DECREASE-KEY O(log n) Sift-up
HEAP-MAXIMUM (peek) O(1) Cukup baca A[1]
Space O(n) Array saja, tanpa pointer

7. Heapsort

Dengan max-heap, kita bisa mengurutkan dalam O(n log n) waktu dan O(1) auxiliary space:

HEAPSORT(A, n)
1   BUILD-MAX-HEAP(A, n)
2   for i = n downto 2
3       swap A[1] and A[i]
4       MAX-HEAPIFY(A, 1, i-1)

Cara Kerja

  1. Bangun max-heap dari array input — sekarang elemen terbesar ada di A[1]
  2. Tukar A[1] dengan A[i] (posisi terakhir dari bagian yang belum terurut) — elemen terbesar sekarang berada di posisi akhir yang benar
  3. Kecilkan heap (abaikan posisi terakhir yang sudah terurut) dan heapify kembali dari root
  4. Ulangi sampai tersisa satu elemen

Analisis Kompleksitas

Komponen Biaya
BUILD-MAX-HEAP O(n)
Loop sebanyak n−1 kali × MAX-HEAPIFY O(log n) O(n log n)
Total time O(n log n)
Auxiliary space O(1) — sepenuhnya in-place

Kenapa Heapsort Menarik

Heapsort adalah satu-satunya algoritma sorting yang sekaligus:

  • O(n log n) di worst case — dijamin, tidak seperti Quick Sort yang bisa O(n²)
  • In-place, O(1) auxiliary space — tidak seperti Merge Sort yang butuh O(n)

Ini menjawab tabel pemilihan algoritma sorting dari Sesi 4: kolom "Best for" untuk Heap Sort tertulis "In-place, predictable" — sekarang kita tahu persis dari mana kedua sifat itu berasal.

8. Ringkasan Perbandingan Space Complexity

Struktur Data Space Operasi Kunci
Array O(n) Access O(1), search O(n)
Stack (array) O(n) Push/Pop O(1)
Queue (circular array) O(n) Enqueue/Dequeue O(1)
Linked List O(n) Insert/Delete head O(1), search O(n)
BST (balanced) O(n) Search/Insert/Delete O(log n)
Heap (array) O(n) Insert/Extract-max O(log n), Max O(1)
Adjacency matrix O(V²) Edge check O(1)
Adjacency list O(V + E) Neighbor iteration O(deg)
Hash table O(n) Insert/Search/Delete O(1) avg

Key takeaway: Heap memberikan trade-off waktu-ruang terbaik untuk operasi priority queue — O(n) space dan O(log n) per update/ekstraksi.

Referensi

Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2022). Introduction to Algorithms, 4th Edition. MIT Press.

  • Ch. 6.1 — Heaps (p. 161)
  • Ch. 6.5 — Priority Queues (p. 172)
  • Ch. 20.1 — Representations of Graphs (p. 549) Skiena, S.S. (2020). The Algorithm Design Manual, 3rd Edition. Springer.
  • Ch. 7.1 — Flavors of Graphs (p. 198)
  • Ch. 7.2 — Data Structures for Graphs (p. 203)
  • Ch. 3.5 — Priority Queues (p. 87)