Heap (Binary Heap)
Terakhir diperbarui
Binary heap adalah complete binary tree yang menyimpan nilai terkecil (min-heap) atau terbesar (max-heap) di root. Visualisasi ini adalah min-heap: setiap induk lebih kecil atau sama dengan anak-anaknya. Untuk menambahkan sebuah nilai, kamu menaruhnya di slot kosong berikutnya, lalu "menaikkannya" (sift up), yaitu menukarnya dengan induknya selama nilainya lebih kecil, sampai sifat heap terpenuhi lagi. Tekan Putar di atas untuk melihat setiap nilai baru naik ke tempatnya.
Karena heap adalah complete tree, heap bisa disimpan secara ringkas di dalam array: anak dari node i ada di 2i+1 dan 2i+2. Penyisipan dan pengambilan nilai minimum bernilai O(log n) (satu jalur dari root ke leaf), sedangkan melihat nilai minimum bernilai O(1), dan itulah persis yang dibutuhkan priority queue.
Kompleksitas waktu dan ruang
| Operasi | Kompleksitas | Catatan |
|---|---|---|
| Lihat min/max (peek) | O(1) | Selalu ada di root |
| Sisipkan (push) | O(log n) | Sift up sepanjang satu jalur |
| Ambil min/max | O(log n) | Sift down sepanjang satu jalur |
| Bangun heap | O(n) | Heapify sekaligus |
| Ruang | O(n) | Berbasis array, tanpa pointer |
Langkah demi langkah (push)
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Tambahkan nilai baru di akhir (leaf kosong berikutnya). |
| 2 | Bandingkan nilai itu dengan induknya. |
| 3 | Jika lebih kecil (min-heap), tukar ke atas. |
| 4 | Ulangi sampai nilainya tidak lagi lebih kecil daripada induknya, atau sudah mencapai root. |
Contoh penerapan
Membangun min-heap dengan melakukan push [5, 3, 8, 1, 4] satu nilai demi satu nilai:
| Push | Array setelah sift-up | Aksi |
|---|---|---|
5 | [5] | Nilai pertama menjadi root. |
3 | [3, 5] | 3 < induk 5, jadi tukar ke atas menjadi root. |
8 | [3, 5, 8] | 8 > induk 5, jadi tetap menjadi leaf. |
1 | [1, 3, 8, 5] | 1 < induk 5, tukar; lalu 1 < induk 3, tukar menjadi root. |
4 | [1, 3, 8, 5, 4] | 4 > induk 3, jadi tetap di tempat; nilai minimum 1 tetap di root. |
Kapan memakai heap
| Pakai saat | Hindari saat |
|---|---|
| Kamu berulang kali butuh item terkecil atau terbesar dari kumpulan data yang terus berubah. | Kamu perlu mencari nilai sembarang, bukan hanya nilai ekstremnya: pakai BST atau hash set. |
| Kamu sedang mengimplementasikan priority queue untuk Dijkstra, A*, atau penjadwal tugas. | Kamu butuh data yang selalu terurut sepenuhnya setiap saat. |
Kamu ingin penyisipan dan pengambilan nilai minimum O(log n) dengan tata letak array yang ringkas. | Kamu butuh pencarian atau penghapusan cepat untuk elemen tertentu (yang bukan root). |
| Kamu perlu menggabungkan aliran item dan mengeluarkannya berdasarkan prioritas. | Datanya sangat kecil dan pemindaian linear lebih sederhana serta sudah cukup cepat. |
Kode Heap (Priority Queue)
Implementasi Heap (Priority Queue) yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Heap (Priority Queue) dalam Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Kode Heap (Priority Queue) dalam JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Kode Heap (Priority Queue) dalam Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Kode Heap (Priority Queue) dalam C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Kode Heap (Priority Queue) dalam C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}FAQ Heap
Untuk apa heap dipakai?
Heap dipakai untuk mengimplementasikan priority queue, yang menggerakkan algoritma jalur terpendek Dijkstra, penjadwal tugas, dan simulasi event. Heap juga menjadi mesin di balik heapsort. Setiap kali kamu berulang kali butuh item terkecil atau terbesar dari kumpulan data yang terus berubah, heap adalah alatnya.
Apa perbedaan heap dan binary search tree?
Keduanya adalah binary tree, tetapi BST menjaga urutan terurut penuh dari kiri ke kanan (sehingga memungkinkan pencarian berurutan), sedangkan heap hanya menjamin hubungan induk dan anak (nilai min atau max di root). Heap memberi akses O(1) ke nilai ekstrem; BST memberi pencarian O(log n) untuk nilai apa pun.
Mengapa heap disimpan di dalam array?
Karena heap selalu berupa complete binary tree, node-nya terpetakan sempurna ke indeks array: anak dari indeks
i ada di 2i+1 dan 2i+2, dan induknya ada di (i-1)/2. Cara ini menghindari penyimpanan pointer anak dan memberi performa cache yang sangat baik.Apakah heap sama dengan array terurut?
Tidak. Heap hanya menjamin setiap induk lebih kecil (min-heap) atau lebih besar (max-heap) daripada anak-anaknya, jadi node yang bersaudara atau bersepupu tidak punya urutan tertentu. Array terurut tersusun penuh, tetapi penyisipannya berbiaya
O(n), sedangkan heap menyisipkan dalam O(log n) sambil tetap memberi akses instan ke nilai ekstrem.Kapan sebaiknya memakai heap, bukan sekadar mengurutkan array?
Pakai heap saat datanya terus berubah dan kamu hanya butuh nilai minimum atau maksimum saat ini: setiap penyisipan dan pengambilan berbiaya
O(log n), dibandingkan mengurutkan ulang seluruh array. Jika datamu statis dan kamu ingin setiap elemen terurut, satu kali pengurutan O(n log n) lebih sederhana dan sering lebih cepat.Apakah membangun heap dari n item butuh O(n log n)?
Tidak, jika kamu membangunnya sekaligus. Menyisipkan
n item satu per satu bernilai O(n log n), tetapi heapify dari bawah ke atas, yang melakukan sift down mulai dari induk terakhir sampai root, secara keseluruhan berjalan dalam O(n), karena sebagian besar node berada di dekat dasar dan hanya turun sejauh jarak yang pendek.Sumber terkait
Visualisasi lainnya
