Sebelum kita mulai, diasumsikan bahwa Anda mengetahui tentang Pohon Biner (dalam pohon biner, setiap node menyimpan kunci yang lebih besar dari semua kunci di subpohon kirinya dan kurang dari semua kunci di subpohon kanannya ) . Sedangkan, Binary Heap adalah pohon biner lengkap yang memenuhi properti pemesanan min-heap atau max-heap. Jika Anda tidak terbiasa dengan konsep ini, kami menyarankan Anda untuk memahaminya sebagai prasyarat. Banyak pemrogram pemula mungkin kesulitan dengan konsep Heaps, Min Heaps, dan Priority Queues. Dalam posting ini kita akan menyelam lebih dalam untuk melihat bagaimana heap berbeda dari Min-Heap dan bagaimana kita dapat menggunakan Priority Queues untuk Menerapkan Min Heap.
Apa itu Min Heap?
Min-heap memiliki properti bahwa setiap node pada level 'n' menyimpan nilai yang kurang dari atau sama dengan anak-anaknya pada level 'n+1'. Karena akar memiliki nilai lebih kecil atau sama dengan anak-anaknya, yang pada gilirannya memiliki nilai lebih kecil atau sama dengan anak-anaknya, akar menyimpan nilai minimum dari semua nilai dalam pohon.
Contoh
Gambar 1: Tumpukan min sederhana
Perhatikan bahwa tidak ada hubungan yang diperlukan antara nilai sebuah node dan saudara kandungnya baik di min-heap atau max-heap. Misalnya, ada kemungkinan bahwa nilai untuk semua simpul di subpohon kiri akar lebih besar daripada nilai untuk setiap simpul di subpohon kanan.
Gambar 2: Min heap dengan node anak kiri > node anak kanan
Representasi Min Heap di Jawa
Struktur data yang paling umum digunakan untuk mewakili Min Heap adalah Array sederhana. Sebagai pemula, Anda tidak perlu bingung antara "array" dengan "min-heap". Anda dapat melihatnya sebagai, nilai node/elemen min-heap disimpan dalam array . Sama seperti kita tidak memiliki struktur data untuk menyimpan " pohon " di Jawa dan kita membangun "simpul" untuknya, atau cara kita menggunakan "peta" untuk menyimpan " grafik ".
Gambar 3: Representasi array dari Heap pada Gambar 2
Kami akan mendemonstrasikan bagaimana Anda dapat dengan mudah mengakses simpul induk, kanan atau kiri anak menggunakan rumus berikut.
Misalkan minHeap[] adalah array integer dengan root pada indeks “ i = 0; ”.
minHeap[(i - 1) / 2] mengembalikan simpul induk.
minHeap[(i * 2) + 2] mengembalikan simpul anak kanan.
minHeap[(i * 2) + 1] mengembalikan simpul anak kiri.
Mempertimbangkan Gambar # 2 yang diberikan di atas, nilai root (induk) = 3, simpul anak kiri adalah 13 dan simpul anak kanan = 7.
Implementasi Min Heap di Java - Menggunakan Array
Mari kita lihat implementasi dasar dari Heaps menggunakan array, dengan index sebagai posisi saat ini dari elemen yang akan ditambahkan, dan size sebagai ukuran total dari array.
import java.util.Arrays;
public class MinHeap
{
private int[] Heap;
private int index;
private int size;
public MinHeap(int size) {
this.size = size;
this.index = 0;
Heap = new int[size];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return (i * 2) + 1;
}
private int rightChild(int i) {
return (i * 2) + 2;
}
private boolean isLeaf(int i) {
if (rightChild(i) >= size || leftChild(i) >= size) {
return true;
}
return false;
}
public void insert(int element) {
if (index >= size) {
return;
}
Heap[index] = element;
int current = index;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
index++;
}
// removes and returns the minimum element from the heap
public int remove() {
// since its a min heap, so root = minimum
int popped = Heap[0];
Heap[0] = Heap[--index];
minHeapify(0);
return popped;
}
// heapify the node at i
private void minHeapify(int i) {
// If the node is a non-leaf node and any of its child is smaller
if (!isLeaf(i)) {
if (Heap[i] > Heap[leftChild(i)] ||
Heap[i] > Heap[rightChild(i)]) {
if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
swap(i, leftChild(i));
minHeapify(leftChild(i));
} else {
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap() {
for (int i = (index - 1 / 2); i >= 1; i--) {
minHeapify(i);
}
}
// Function to print the contents of the heap
public void printHeap() {
for (int i = 0; i < (index / 2); i++) {
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < index)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < index)
System.out.print(" Right :" + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
private void swap(int x, int y) {
int tmp;
tmp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = tmp;
}
public static void main(String[] arg)
{
MinHeap minHeap = new MinHeap(7);
minHeap.insert(3);
minHeap.insert(13);
minHeap.insert(7);
minHeap.insert(16);
minHeap.insert(21);
minHeap.insert(12);
minHeap.insert(9);
minHeap.minHeap();
System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
minHeap.printHeap();
System.out.println("\nThe Min Value is : " + minHeap.remove());
System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
minHeap.printHeap();
}
}
Keluaran
Min Heap adalah : [3, 13, 7, 16, 21, 12, 9] Induk : 3 Kiri : 13 Kanan :7 Induk : 13 Kiri : 16 Kanan :21 Induk : 7 Kiri : 12 Kanan :9 Nilai Min adalah : 3 Tumpukan Min adalah : [7, 13, 9, 16, 21, 12, 9] // setelah menghapus akar Induk : 7 Kiri : 13 Kanan :9 Induk : 13 Kiri : 16 Kanan :21 Induk : 9 Kiri : 12
Antrian Prioritas
Antrian Prioritas adalah jenis antrian khusus di mana setiap elemen dikaitkan dengan prioritas dan ditempatkan sesuai dengan prioritasnya. Untuk implementasi min heap yang lebih mudah, kami menggunakan kelas PriorityQueue java.util.PriorityQueue yang disediakan oleh Java. Jika elemen yang diberikan seharusnya diurutkan/ditempatkan dalam prioritas maka Antrian Prioritas digunakan. Antrean Prioritas berbeda dengan Antrian sederhana karena antrean standar mengikuti algoritma First-In-First-Out ( FIFO ), tetapi terkadang elemen antrean perlu diproses sesuai dengan prioritas, oleh karena itu dirancang Antrian Prioritas. Saat Anda menambahkan elemen ke antrean prioritas, min heap dibuat secara default.
Operasi Umum
Sebelum kita beralih ke implementasi, berikut adalah beberapa operasi umum di java.util.PriorityQueue yang perlu Anda ketahui.
add(int element) menyisipkan elemen yang ditentukan dalam antrian prioritas.
remove(int element) menghapus satu instance dari elemen yang ditentukan dari antrian ini, jika ada.
peek() mengambil, tetapi tidak menghapus, kepala antrean ini, atau mengembalikan nol jika antrean kosong.
poll() mengambil dan menghapus kepala antrean ini, atau mengembalikan nol jika antrean ini kosong.
berisi () mengembalikan "benar" jika antrian ini berisi elemen yang ditentukan.
size() mengembalikan jumlah elemen dalam antrian/minheap prioritas ini.
Implementasi Min Heap di Java menggunakan Priority Queues
Inilah cara Anda dapat mengimplementasikan min heap menggunakan kelas antrian prioritas dengan java.
import java.util.*;
class MinHeapPriorityQueue {
static PriorityQueue minHeap = new PriorityQueue();
public static void view() {
for (Integer x : minHeap) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String args[]) {
// using "add" operation to insert elements
minHeap.add(3);
System.out.print("minHeap.add(3) = ");
view();
minHeap.add(13);
minHeap.add(7);
minHeap.add(16);
minHeap.add(21);
minHeap.add(12);
minHeap.add(9);
// printing Min-Heap
System.out.print("minHeap.view() = ");
view();
// using "peek" method to view the head
System.out.println("minHeap.peek() = " + minHeap.peek());
// using "poll" method to remove and retrieve the head
minHeap.poll();
System.out.print("minHeap.poll() = ");
view();
// using "remove" method to remove specified element
minHeap.remove(7);
System.out.print("minHeap.remove(7) = ");
view();
// Check if an element is present using contains()
boolean elementFound = minHeap.contains(11);
System.out.println("minHeap.contains(11) = " + elementFound);
elementFound = minHeap.contains(16);
System.out.println("minHeap.contains(16) = " + elementFound);
}
}
Tumpukan min banyak digunakan untuk mengambil elemen terkecil dalam kumpulan elemen dalam waktu konstan. Ada banyak aplikasi lain dari struktur data ini, namun Anda dapat memilih metode apa pun untuk mengimplementasikannya. Tak perlu dikatakan, Anda harus berlatih dengan kesabaran untuk menjadi ahli dalam hal itu. Jadi, ayo gerakkan otot kita dan mulai bekerja!
GO TO FULL VERSION