Innan vi börjar antas det att du känner till ett binärt träd (i ett binärt träd lagrar varje nod en nyckel som är större än alla nycklar i dess vänstra underträd och mindre än alla nycklar i dess högra underträd ) . Medan en binär heap är ett komplett binärt träd som uppfyller antingen min-heap- eller max-heap- orderegenskapen. Om du inte är bekant med dessa begrepp rekommenderar vi att du förstår dessa som en förutsättning. Många nybörjare programmerare kan kämpa med konceptet Heaps, Min Heaps och Priority Queue. I det här inlägget tar vi en djupdykning för att se hur heaps skiljer sig från Min-Heaps och hur vi kan använda prioriterade köer för att implementera Min-heaps.
Vad är en Min Heap?
En min-hög har egenskapen att varje nod på nivå 'n' lagrar ett värde som är mindre än eller lika med dess underordnade värde på nivå 'n+1'. Eftersom roten har ett värde som är mindre än eller lika med dess barn, som i sin tur har värden mindre än eller lika med deras barn, lagrar roten minimum av alla värden i trädet.
Exempel
Figur 1: En enkel min hög
Observera att det inte finns något nödvändigt samband mellan värdet av en nod och värdet för dess syskon i varken min-högen eller maxhögen. Till exempel är det möjligt att värdena för alla noder i rotens vänstra delträd är större än värdena för varje nod i det högra underträdet.
Figur 2: Min hög med vänstra barnnoder > höger undernoder
Representation av Min Heap i Java
Den vanligaste datastrukturen för att representera en Min Heap är en enkel Array. Som nybörjare behöver du inte blanda ihop en "array" med en "min-heap". Du kan se det som att värdena för noder/element i en min-hög lagras i en array . Precis som att vi inte har någon datastruktur för att lagra ett " träd " i Java och vi bygger en "nod" för det, eller hur vi använder "karta" för att lagra en " graf ".
Figur 3: Arrayrepresentation av högen i figur 2
Vi kommer att visa hur du enkelt kan komma åt föräldernoderna, höger eller vänster underordnade noder med hjälp av följande formler.
Låt minHeap[] är en heltalsmatris med rot vid index " i = 0; ”.
minHeap[(i - 1) / 2] returnerar den överordnade noden.
minHeap[(i * 2) + 2] returnerar den högra underordnade noden.
minHeap[(i * 2) + 1] returnerar den vänstra underordnade noden.
Med tanke på figur # 2 ovan är värdet på rot (förälder) = 3, vänster undernod är 13 och höger undernod = 7.
Implementering av Min Heap i Java - Använda arrayer
Låt oss titta på den grundläggande implementeringen av Heaps med array, med index som den aktuella positionen för elementet som ska läggas till, och storlek som den totala storleken på arrayen.
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();
}
}
Produktion
Minsta högen är : [3, 13, 7, 16, 21, 12, 9] Förälder : 3 Vänster : 13 Höger :7 Förälder : 13 Vänster : 16 Höger :21 Förälder : 7 Vänster : 12 Höger :9 Minsta värdet är : 3 Minsta högen är : [7, 13, 9, 16, 21, 12, 9] // efter att ha tagit bort roten Förälder : 7 Vänster : 13 Höger :9 Förälder : 13 Vänster : 16 Höger :21 Förälder : 9 Vänster: 12
Prioriterade köer
En Priority Queue är en speciell typ av kö där varje element är associerat med en prioritet och placeras enligt dess prioritet. För en enklare implementering av min heap använder vi PriorityQueue-klassen java.util.PriorityQueue från Java. Om de givna elementen ska sorteras/placeras i en prioritet används en Priority Queue. En Priority Queue skiljer sig från en enkel Queue eftersom standardköerna följer First-In-First-Out ( FIFO ) algoritmen, men ibland behöver köns element bearbetas enligt prioritet, det är därför Priority Queue är designad. När du lägger till element i en prioriterad kö, byggs en min-hög som standard.
Gemensamma operationer
Innan vi går vidare till implementeringen här är några vanliga operationer i java.util.PriorityQueue som du behöver känna till.
add(int element) infogar det angivna elementet i en prioritetskö.
remove(int element) tar bort en enda instans av det angivna elementet från den här kön, om det finns.
peek() hämtar, men tar inte bort, huvudet på denna kö, eller returnerar null om kön är tom.
poll() hämtar och tar bort huvudet på denna kö, eller returnerar null om denna kö är tom.
contains() returnerar "true" om denna kö innehåller det angivna elementet.
size() returnerar antalet element i denna prioritetskö/minheap.
Implementering av Min Heap i Java med hjälp av Priority Queue
Så här kan du implementera en min-hög med prioritetsköklass av 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);
}
}
Minhögar används ofta för att hämta det minsta elementet i en pool av element i konstant tid. Det finns många andra tillämpningar av denna datastruktur, men du kan välja vilken metod som helst för att implementera detta. Det behöver inte sägas att du måste träna med tålamod för att bli bra på det. Så låt oss få igång våra muskler och börja jobba!
GO TO FULL VERSION