🏔️ Heap dan Priority Queue

Struktur Data dan Algoritma

Pertemuan 13

Universitas Pertahanan RI

🎯 Tujuan Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Menjelaskan konsep heap dan membedakan max-heap vs min-heap
Mengidentifikasi properti heap (complete binary tree + heap property)
Menerapkan representasi heap menggunakan array
Mengimplementasikan operasi insert dan extract
Membangun heap dari array dengan kompleksitas O(n)
Mengimplementasikan Priority Queue dan Heap Sort

📋 Agenda

Bagian 1

Konsep Heap
Representasi Array
Operasi Insert (Percolate Up)
Operasi Extract (Percolate Down)

Bagian 2

Build Heap
Priority Queue
Heap Sort
Perbandingan & Aplikasi

📖 1. Konsep Heap

Heap adalah struktur data berbentuk complete binary tree yang memenuhi heap property.

Heap menyediakan akses ke elemen dengan prioritas tertinggi/terendah dalam O(1)

Max-Heap vs Min-Heap

🔺 Max-Heap

Parent ≥ semua children

Root = Maximum

90
85 70

🔻 Min-Heap

Parent ≤ semua children

Root = Minimum

10
20 30

Complete Binary Tree

Semua level terisi penuh kecuali mungkin level terakhir, dan level terakhir diisi dari kiri ke kanan.

Properti	Nilai
Tinggi tree (n node)	`⌊log₂ n⌋`
Jumlah node level h	`2^h`
Selalu balanced	✅ Ya

Properti ini memungkinkan representasi efisien dengan array!

🧠 Quiz: Valid Heap?

Manakah yang merupakan max-heap yang valid?

A. [50, 40, 30, 35, 25]

B. [50, 60, 30, 35, 25]

Jawaban: A

B tidak valid karena 60 > 50 (child > parent)

📖 2. Representasi Array

Heap dapat disimpan dalam array dengan formula navigasi sederhana:

Formula Navigasi

Operasi	Formula (index 0-based)	Contoh (i = 1)
Parent	`(i - 1) / 2`	Parent(1) = 0
Left Child	`2 * i + 1`	Left(1) = 3
Right Child	`2 * i + 2`	Right(1) = 4

💡 Tidak perlu pointer! Navigasi tree hanya dengan kalkulasi indeks.

💻 Implementasi Dasar


class MaxHeap {
private:
    vector<int> heap;
    
    int parent(int i) { return (i - 1) / 2; }
    int leftChild(int i) { return 2 * i + 1; }
    int rightChild(int i) { return 2 * i + 2; }
    
public:
    bool isEmpty() { return heap.empty(); }
    int size() { return heap.size(); }
    
    int getMax() {
        if (isEmpty()) throw runtime_error("Heap kosong!");
        return heap[0];  // Root = maximum
    }
};

📖 3. Operasi Insert

Percolate Up (Bubble Up)

Tambahkan elemen baru di posisi terakhir
Percolate up: Bandingkan dengan parent, swap jika perlu
Ulangi sampai heap property terpenuhi

Kompleksitas: O(log n)

Insert: Contoh Visual

Insert 95 ke max-heap [90, 85, 70]

Step 1: Tambah 95 di akhir → [90, 85, 70, 95]

Step 2: 95 > 85 (parent)? ✅ Swap → [90, 95, 70, 85]

Step 3: 95 > 90 (parent)? ✅ Swap → [95, 90, 70, 85]

✅ Selesai! 95 menjadi root baru

💻 Kode Insert


void insert(int value) {
    // 1. Tambah di akhir
    heap.push_back(value);
    
    // 2. Percolate up
    int index = heap.size() - 1;
    while (index > 0 && heap[index] > heap[parent(index)]) {
        swap(heap[index], heap[parent(index)]);
        index = parent(index);
    }
}  // Kompleksitas: O(log n)

📖 4. Operasi Extract

Percolate Down (Bubble Down)

Simpan nilai root (yang akan dikembalikan)
Pindahkan elemen terakhir ke root
Percolate down: Swap dengan child terbesar jika perlu
Ulangi sampai heap property terpenuhi

Kompleksitas: O(log n)

Extract: Contoh Visual

ExtractMax dari [90, 85, 70, 40, 50]

Step 1: Simpan max = 90

Step 2: Pindah 50 ke root → [50, 85, 70, 40]

Step 3: 50 < 85? ✅ Swap dengan child terbesar → [85, 50, 70, 40]

✅ Return 90 | Heap valid: [85, 50, 70, 40]

💻 Kode Extract


int extractMax() {
    if (isEmpty()) throw runtime_error("Heap kosong!");
    
    int maxVal = heap[0];           // Simpan max
    heap[0] = heap.back();          // Pindah last ke root
    heap.pop_back();
    
    if (!heap.empty()) {
        percolateDown(0);           // Fix heap property
    }
    return maxVal;
}

void percolateDown(int index) {
    int n = heap.size();
    int largest = index;
    int left = leftChild(index), right = rightChild(index);
    
    if (left < n && heap[left] > heap[largest]) largest = left;
    if (right < n && heap[right] > heap[largest]) largest = right;
    
    if (largest != index) {
        swap(heap[index], heap[largest]);
        percolateDown(largest);     // Rekursi
    }
}

🧠 Quiz: Percolate Down

Setelah extractMax dari [100, 90, 80, 70, 60, 50, 40], apa hasilnya?

Hint: Pindah 40 ke root, lalu percolate down

Hasil: [90, 70, 80, 40, 60, 50]

40 → swap dengan 90 → swap dengan 70 → selesai

📖 5. Build Heap

Algoritma Floyd (Bottom-Up)

Pendekatan	Metode	Kompleksitas
Top-down	Insert satu per satu	O(n log n)
Bottom-up (Floyd)	Heapify dari node internal terakhir	O(n)

Insight Algoritma Floyd

💡 Semua leaf node sudah merupakan heap yang valid (heap dengan 1 elemen). Kita hanya perlu memperbaiki node internal.

Mulai dari node internal terakhir: i = n/2 - 1

Heapify mundur sampai root: i = 0

💻 Kode Build Heap


void buildHeap(vector<int>& arr) {
    int n = arr.size();
    // Mulai dari node internal terakhir
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void heapify(vector<int>& arr, int n, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    if (largest != index) {
        swap(arr[index], arr[largest]);
        heapify(arr, n, largest);
    }
}

Contoh Build Heap

Array: [4, 10, 3, 5, 1] → Build max-heap

n=5, mulai dari i = 5/2 - 1 = 1

Heapify(1): 10 > 5, 10 > 1 ✅ tidak berubah

Heapify(0): 4 < 10? Swap! → [10, 4, 3, 5, 1]

Rekursi: 4 < 5? Swap! → [10, 5, 3, 4, 1]

✅ Hasil: [10, 5, 3, 4, 1]

Mengapa O(n)?

📊 Node di level h dari bawah: ~n/2^(h+1)

📊 Operasi per node level h: maksimal h swap

📊 Total: Σ (h × n/2^(h+1)) = O(n)

💡 Lebih banyak node di level bawah dengan jarak pendek ke posisi final!

📖 6. Priority Queue

Priority Queue adalah ADT di mana setiap elemen memiliki prioritas, dan elemen dengan prioritas tertinggi selalu diakses lebih dulu.

ADT Priority Queue


ADT PriorityQueue:
  Data:
    - Kumpulan elemen dengan prioritas
    
  Operasi:
    - insert(item, priority): Tambah elemen dengan prioritas
    - extractMax(): Hapus & kembalikan elemen prioritas tertinggi
    - peek(): Lihat elemen prioritas tertinggi tanpa hapus
    - isEmpty(): Cek apakah kosong
    
  Implementasi:
    - Array tidak terurut: Insert O(1), Extract O(n)
    - Array terurut: Insert O(n), Extract O(1)
    - HEAP: Insert O(log n), Extract O(log n) ← OPTIMAL!

Queue vs Priority Queue

Aspek	Queue (FIFO)	Priority Queue
Urutan keluar	First In First Out	Berdasarkan prioritas
Dequeue	Elemen tertua	Elemen prioritas tertinggi
Insert	O(1)	O(log n) dengan heap
Contoh	Antrian kasir	Sistem scheduling task

🎖️ Aplikasi Pertahanan

Sistem Alert Prioritas

Prioritas 10: Serangan siber kritis
Prioritas 7: Intrusi terdeteksi
Prioritas 3: Anomali minor


pq.insert(Task("Serangan DDoS", 10));
pq.insert(Task("Login mencurigakan", 7));
pq.insert(Task("Traffic anomaly", 3));

// Proses berdasarkan prioritas
pq.extractMax(); // → "Serangan DDoS" (prioritas 10)

📖 7. Heap Sort

Heap Sort = Build max-heap + Extract max berulang kali

Phase 1: Build max-heap dari array → O(n)
Phase 2: Extract max n kali, tempatkan di akhir → O(n log n)

Heap Sort: Visualisasi

Array: [4, 10, 3, 5, 1]

Phase 1 (Build): → [10, 5, 3, 4, 1]

Phase 2 (Extract):

Swap 10↔1, heapify: [5, 4, 3, 1 | 10]

Swap 5↔1, heapify: [4, 1, 3 | 5, 10]

Swap 4↔3, heapify: [3, 1 | 4, 5, 10]

Swap 3↔1: [1 | 3, 4, 5, 10]

✅ Hasil: [1, 3, 4, 5, 10]

💻 Kode Heap Sort


void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    // Phase 1: Build max-heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // Phase 2: Extract elements one by one
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);   // Pindah max ke akhir
        heapify(arr, i, 0);     // Heapify reduced heap
    }
}

Heap Sort vs Lainnya

Algoritma	Best	Average	Worst	Space	Stable
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌

Heap Sort: worst-case O(n log n) + in-place O(1)

Kapan Gunakan Heap Sort?

✅ Gunakan ketika:

Memori terbatas (in-place)
Perlu jaminan O(n log n)
Data besar & random

⚠️ Pertimbangkan lain:

Perlu stable sort → Merge
Data hampir terurut → Insertion
Praktik umum → Quick Sort

📝 Ringkasan

Konsep	Deskripsi	Kompleksitas
Heap	Complete binary tree + heap property	-
Max/Min-Heap	Parent ≥/≤ children, root = max/min	-
Insert	Tambah di akhir + percolate up	O(log n)
Extract	Ambil root, last→root + percolate down	O(log n)
Peek	Lihat root tanpa hapus	O(1)
Build Heap	Floyd's algorithm (bottom-up)	O(n)
Priority Queue	ADT dengan akses berdasarkan prioritas	Insert/Extract: O(log n)
Heap Sort	Build heap + extract n kali	O(n log n), in-place

❓ Pertanyaan?

Silakan bertanya atau diskusi

Referensi: Cormen Ch.6 | Weiss Ch.6 | Hubbard Ch.12

Terima Kasih! 🙏

Struktur Data dan Algoritma

Pertemuan 13