Sebelum kita bermula, diandaikan bahawa anda tahu tentang Pokok Binari (dalam pokok binari, setiap nod menyimpan kunci yang lebih besar daripada semua kunci dalam subpokok kiri dan kurang daripada semua kunci dalam subpokok kanannya ) . Manakala, Binary Heap ialah pokok binari lengkap yang memenuhi sama ada timbunan min atau harta pesanan timbunan maks.. Jika anda tidak biasa dengan konsep ini, kami mengesyorkan anda memahaminya sebagai prasyarat. Ramai pengaturcara baru boleh bergelut dengan konsep Heaps, Min Heaps dan Priority Queues. Dalam siaran ini, kami akan menyelam secara mendalam untuk melihat cara timbunan berbeza daripada Timbunan Min dan cara kami boleh menggunakan Baris Keutamaan untuk Melaksanakan Timbunan Min.
Apakah Tumpukan Min?
Timbunan min mempunyai sifat bahawa setiap nod pada tahap 'n' menyimpan nilai yang kurang daripada atau sama dengan nilai anak-anaknya pada tahap 'n+1'. Oleh kerana akar mempunyai nilai kurang daripada atau sama dengan anak-anaknya, yang seterusnya mempunyai nilai kurang daripada atau sama dengan anak-anak mereka, akar menyimpan minimum semua nilai dalam pokok.
Contoh
Rajah 1: Timbunan min mudah
Ambil perhatian bahawa tiada perhubungan yang diperlukan antara nilai nod dan adik-beradiknya sama ada dalam timbunan min atau timbunan maks. Sebagai contoh, ada kemungkinan bahawa nilai untuk semua nod dalam subpokok kiri akar lebih besar daripada nilai untuk setiap nod subpokok kanan.
Rajah 2: Timbunan min dengan nod anak kiri > nod anak kanan
Perwakilan Min Heap di Jawa
Struktur data yang paling biasa digunakan untuk mewakili Timbunan Min ialah Tatasusunan mudah. Sebagai seorang pemula, anda tidak perlu mengelirukan "tatasusunan" dengan "timbunan min". Anda boleh melihatnya sebagai, nilai nod / elemen timbunan min disimpan dalam tatasusunan . Sama seperti kami tidak mempunyai sebarang struktur data untuk menyimpan " pokok " di Jawa dan kami membina "nod" untuknya, atau cara kami menggunakan "peta" untuk menyimpan " graf ".
Rajah 3: Perwakilan tatasusunan bagi Timbunan dalam Rajah 2
Kami akan menunjukkan cara anda hanya boleh mengakses nod anak induk, kanan atau kiri menggunakan formula berikut.
Biarkan minHeap[] ialah tatasusunan integer dengan punca pada indeks “ i = 0; ”.
minHeap[(i - 1) / 2] mengembalikan nod induk.
minHeap[(i * 2) + 2] mengembalikan nod anak kanan.
minHeap[(i * 2) + 1] mengembalikan nod anak kiri.
Memandangkan Rajah # 2 yang diberikan di atas, nilai punca (induk) = 3, nod anak kiri ialah 13 dan nod anak kanan = 7.
Pelaksanaan Min Heap dalam Java - Menggunakan Tatasusunan
Mari kita lihat pelaksanaan asas Heaps menggunakan tatasusunan, dengan indeks sebagai kedudukan semasa elemen yang akan ditambah, dan saiz sebagai jumlah saiz tatasusunan.
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();
}
}
Pengeluaran
Timbunan Min ialah : [3, 13, 7, 16, 21, 12, 9] Ibu Bapa : 3 Kiri : 13 Kanan :7 Ibu Bapa : 13 Kiri : 16 Kanan :21 Ibu Bapa : 7 Kiri : 12 Kanan :9 Nilai Min ialah : 3 Timbunan Min ialah : [7, 13, 9, 16, 21, 12, 9] // selepas mengeluarkan akar Induk : 7 Kiri : 13 Kanan :9 Ibu Bapa : 13 Kiri : 16 Kanan :21 Ibu Bapa : 9 Kiri: 12
Barisan Keutamaan
Barisan Keutamaan ialah jenis baris gilir khas di mana setiap elemen dikaitkan dengan keutamaan dan diletakkan mengikut keutamaannya. Untuk pelaksanaan timbunan min yang lebih mudah, kami menggunakan kelas PriorityQueue java.util.PriorityQueue yang disediakan oleh Java. Jika elemen yang diberikan sepatutnya diisih/diletakkan dalam keutamaan maka Gilir Keutamaan digunakan. Baris Keutamaan adalah berbeza daripada Baris Gilir mudah kerana baris gilir standard mengikut algoritma First-In-First-Out ( FIFO ), tetapi kadangkala elemen baris gilir perlu diproses mengikut keutamaan, itulah sebabnya Gilir Keutamaan direka bentuk. Apabila anda menambah elemen pada baris gilir keutamaan, timbunan min dibina secara lalai.
Operasi Biasa
Sebelum kita beralih kepada pelaksanaan di sini ialah beberapa operasi biasa dalam java.util.PriorityQueue yang perlu anda ketahui.
add(int element) memasukkan elemen yang ditentukan dalam baris gilir keutamaan.
remove(int element) mengalih keluar satu contoh elemen yang ditentukan daripada baris gilir ini, jika ia ada.
peek() mendapatkan semula, tetapi tidak mengalih keluar, kepala baris gilir ini, atau mengembalikan null jika baris gilir kosong.
poll() mengambil dan mengalih keluar kepala baris gilir ini, atau mengembalikan null jika baris gilir ini kosong.
contains() mengembalikan "true" jika baris gilir ini mengandungi elemen yang ditentukan.
size() mengembalikan bilangan elemen dalam baris gilir keutamaan ini/minheap.
Pelaksanaan Min Heap di Java menggunakan Barisan Keutamaan
Begini cara anda boleh melaksanakan timbunan min menggunakan kelas gilir keutamaan oleh 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);
}
}
Timbunan min digunakan secara meluas untuk mendapatkan semula elemen terkecil dalam kumpulan elemen dalam masa tetap. Terdapat banyak aplikasi lain struktur data ini, namun anda boleh memilih mana-mana kaedah untuk melaksanakan ini. Tidak perlu dikatakan, anda perlu berlatih dengan kesabaran untuk menguasainya. Jadi mari kita gerakkan otot kita dan mulakan kerja!
GO TO FULL VERSION