Heap dan Priority Queue

---

🧭 1. Pengertian Heap

7

📖 Definisi

Heap adalah struktur data berbentuk binary tree lengkap (complete binary tree) yang memenuhi aturan khusus:

• Max Heap: parent ≥ child
• Min Heap: parent ≤ child

---

🧠 Narasi Konseptual

Bayangkan tumpukan prioritas pekerjaan:

• Pekerjaan paling penting selalu di atas
• Pekerjaan lain mengikuti aturan prioritas

➡️ Heap digunakan untuk memastikan data paling prioritas selalu mudah diakses.

---

🎯 2. Karakteristik Heap

📊 Tabel Karakteristik

Karakteristik	Penjelasan
Bentuk	Complete Binary Tree
Aturan	Heap property (min/max)
Akses utama	Elemen root
Struktur	Tidak fully sorted

---

🧠 Narasi

Heap bukan struktur yang sepenuhnya terurut, tetapi:

• Hanya menjamin elemen paling prioritas ada di root

---

🌲 3. Jenis Heap

---

🔹 A. Max Heap

7

📖 Konsep

• Parent selalu lebih besar dari child
• Root = nilai terbesar

---

🧠 Narasi

Seperti sistem ranking:

• Juara 1 selalu di puncak

---

🔹 B. Min Heap

6

📖 Konsep

• Parent selalu lebih kecil dari child
• Root = nilai terkecil

---

🧠 Narasi

Seperti antrian cepat:

• Paling kecil (paling prioritas) diproses dulu

---

🧱 4. Struktur Heap (Complete Binary Tree)

7

📖 Konsep

Heap harus complete binary tree:

• Semua level penuh
• Kecuali level terakhir (diisi dari kiri ke kanan)

---

🧮 5. Representasi Heap dalam Array

📊 Rumus Index

Hubungan	Rumus
Parent	(i – 1) / 2
Left Child	2i + 1
Right Child	2i + 2

---

🧠 Narasi

Heap tidak perlu pointer:

• Semua node disimpan dalam array
• Posisi ditentukan secara matematis

---

⚙️ 6. Operasi Heap

📊 Tabel Operasi

Operasi	Deskripsi	Kompleksitas
Insert	Menambah elemen	O(log n)
Delete (root)	Menghapus elemen prioritas	O(log n)
Peek	Melihat root	O(1)

---

➕ 7. Insert pada Heap

6

📖 Proses

1. Tambah di posisi terakhir
2. Bandingkan dengan parent
3. Tukar jika melanggar aturan
4. Ulangi (heapify up)

---

🧠 Narasi

Seperti anak baru:

• Masuk ke bawah dulu
• Naik jika lebih “prioritas”

---

➖ 8. Delete (Heapify Down)

7

📖 Proses

1. Hapus root
2. Ganti dengan elemen terakhir
3. Turunkan (heapify down)
4. Perbaiki struktur heap

---

🧠 Narasi

Seperti mengganti pimpinan:

• Posisi atas diganti
• Struktur disesuaikan ulang

---

🔁 9. Heapify Process

📖 Definisi

Heapify adalah proses memperbaiki struktur heap agar tetap memenuhi aturan min/max heap.

---

📌 10. Priority Queue (Antrian Prioritas)

7

📖 Definisi

Priority Queue adalah struktur data di mana setiap elemen memiliki prioritas, dan elemen dengan prioritas tertinggi diproses terlebih dahulu.

---

🧠 Narasi

Berbeda dengan queue biasa:

• Queue biasa → FIFO
• Priority Queue → berdasarkan prioritas

---

🏥 11. Contoh Kehidupan Nyata

Sistem	Implementasi
Rumah sakit	Pasien darurat duluan
CPU Scheduling	Proses prioritas tinggi
Jaringan	Paket data prioritas
Game	Event penting lebih dulu

---

⚖️ 12. Heap vs Queue vs Stack

📊 Tabel Perbandingan

Struktur	Prinsip	Akses
Stack	LIFO	Top
Queue	FIFO	Front
Priority Queue	Priority	Root (heap)

---

⏱️ 13. Kompleksitas Heap

📊 Tabel Kompleksitas

Operasi	Kompleksitas
Insert	O(log n)
Delete	O(log n)
Peek	O(1)

---

🧠 14. Kelebihan Heap

📌 Narasi

Heap sangat penting karena:

• Efisien untuk prioritas data
• Digunakan di algoritma graf
• Digunakan dalam sistem scheduling

---

⚠️ 15. Kekurangan Heap

📊 Tabel

Kekurangan	Penjelasan
Tidak fully sorted	Hanya root yang pasti
Akses terbatas	Tidak bisa random access
Kompleks	Implementasi agak sulit

---

🧪 16. Studi Kasus Nyata

📌 Dijkstra Algorithm

• Heap digunakan untuk memilih node dengan jarak terkecil

---

📌 Task Scheduling OS

• Proses prioritas tinggi dijalankan lebih dulu

---

💻 17. Implementasi Sederhana (C++)

#include <queue>
#include <iostream>
using namespace std;int main(){
    priority_queue<int> pq; // max heap    pq.push(10);
    pq.push(5);
    pq.push(20);    cout << pq.top(); // 20
}

---

📚 18. Ringkasan Materi

• Heap adalah complete binary tree dengan aturan prioritas
• Ada max heap dan min heap
• Priority queue menggunakan heap
• Operasi utama: insert, delete, peek
• Digunakan dalam sistem real seperti OS dan jaringan

---

📝 19. Latihan / Diskusi

✏️ Soal Teori

1. Jelaskan heap dan jenisnya
2. Apa itu priority queue?
3. Bedakan heap dan queue biasa

💻 Soal Praktikum

1. Implementasikan max heap sederhana
2. Simulasikan priority queue
3. Tambahkan dan hapus elemen heap

---

🎯 Penutup

Heap dan Priority Queue adalah struktur data penting untuk sistem berbasis prioritas, terutama dalam:

• Operating System
• Networking
• Artificial Intelligence
• Graph Algorithm