Før vi går i gang, antages det, at du kender til et binært træ (i et binært træ gemmer hver node en nøgle, der er større end alle nøglerne i dets venstre undertræ og mindre end alle nøglerne i dets højre undertræ ) . Hvorimod en binær heap er et komplet binært træ, der opfylder enten min-heap- eller max-heap- bestillingsegenskaben. Hvis du ikke er bekendt med disse begreber, anbefaler vi, at du forstår disse som en forudsætning. Mange uerfarne programmører kan kæmpe med konceptet Heaps, Min Heaps og Priority Queue. I dette indlæg tager vi et dybt dyk for at se, hvordan heaps er forskellige fra Min-Heaps, og hvordan vi kan bruge Priority Queue til at implementere Min-Heaps.
Hvad er en Min Heap?
En min-heap har den egenskab, at hver node på niveau 'n' gemmer en værdi, der er mindre end eller lig med værdien for dens børn på niveau 'n+1'. Fordi roden har en værdi mindre end eller lig med dens børn, som igen har værdier mindre end eller lig med deres børn, gemmer roden minimum af alle værdier i træet.
Eksempel
Figur 1: En simpel min heap
Bemærk, at der ikke er noget nødvendigt forhold mellem værdien af en node og værdien af dens søskende i hverken min-heapen eller max-heapen. For eksempel er det muligt, at værdierne for alle noder i det venstre undertræ af roden er større end værdierne for hver knude i det højre undertræ.
Figur 2: Min bunke med venstre underordnede knudepunkter > højre underordnede knudepunkter
Repræsentation af Min Heap i Java
Den mest almindeligt anvendte datastruktur til at repræsentere en Min Heap er en simpel Array. Som nybegynder behøver du ikke forveksle en "array" med en "min-heap". Du kan se på det som, at værdierne af noder/elementer i en min-heap er gemt i et array . Ligesom vi ikke har nogen datastruktur til at gemme et " træ " i Java, og vi bygger en "node" til det, eller den måde, vi bruger "kort" til at gemme en " graf ".
Figur 3: Array-repræsentation af heapen i figur 2
Vi skal demonstrere, hvordan du blot kan få adgang til de overordnede, højre eller venstre underordnede noder ved hjælp af følgende formler.
Lad minHeap[] er et heltalsarray med rod ved indeks " i = 0; ”.
minHeap[(i - 1) / 2] returnerer den overordnede node.
minHeap[(i * 2) + 2] returnerer den rigtige underordnede node.
minHeap[(i * 2) + 1] returnerer den venstre underordnede node.
I betragtning af figur # 2 ovenfor er værdien af rod (forælder) = 3, venstre underknude er 13 og højre underknude = 7.
Implementering af Min Heap i Java - Brug af arrays
Lad os se på den grundlæggende implementering af Heaps ved hjælp af array, med indeks som den aktuelle position for det element, der skal tilføjes, og størrelse som den samlede størrelse af arrayet.
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();
}
}
En prioritetskø er en speciel type kø, hvor hvert element er knyttet til en prioritet og placeres i henhold til dets prioritet. For en lettere implementering af min heap bruger vi PriorityQueue-klassen java.util.PriorityQueue leveret af Java. Hvis de givne elementer formodes at være sorteret/placeret i en prioritet, bruges en Priority Queue. En Priority Queue er forskellig fra en simpel kø, fordi standardkøerne følger FIFO -algoritmen (First-In-First-Out), men nogle gange skal elementerne i køen behandles i henhold til prioriteten, det er derfor, Priority Queue er designet. Når du tilføjer elementer til en prioritetskø, bygges der som standard en min heap.
Fælles operationer
Før vi går videre til implementeringen, er her et par almindelige operationer i java.util.PriorityQueue , som du har brug for at kende.
add(int element) indsætter det angivne element i en prioritetskø.
remove(int element) fjerner en enkelt forekomst af det angivne element fra denne kø, hvis det er til stede.
peek() henter, men fjerner ikke, hovedet af denne kø eller returnerer null, hvis køen er tom.
poll() henter og fjerner hovedet af denne kø, eller returnerer null, hvis denne kø er tom.
contains() returnerer "true", hvis denne kø indeholder det angivne element.
size() returnerer antallet af elementer i denne prioritetskø/minheap.
Implementering af Min Heap i Java ved hjælp af Priority Queue
Her er, hvordan du kan implementere en min heap ved hjælp af prioritetskøklasse af 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);
}
}
Mine dynger er meget brugt til at hente det mindste element i en pulje af elementer i konstant tid. Der er masser af andre applikationer af denne datastruktur, men du kan vælge en hvilken som helst metode til at implementere dette. Det er overflødigt at sige, at du skal øve dig med tålmodighed for at blive god til det. Så lad os få vores muskler i gang og komme i gang!
GO TO FULL VERSION