Min haug i Java med eksempler

Før vi begynner, antas det at du kjenner til et binært tre (i et binært tre lagrer hver node en nøkkel som er større enn alle nøklene i venstre undertre og mindre enn alle nøklene i høyre undertre ) . Mens en binær haug er et komplett binært tre som tilfredsstiller enten min-heap- eller max-heap- bestillingsegenskapen. Hvis du ikke er kjent med disse konseptene, anbefaler vi at du forstår disse som en forutsetning. Mange nybegynnere programmerere kan slite med konseptet Heaps, Min Heaps og Priority Queue. I dette innlegget tar vi et dypdykk for å se hvordan heaps er forskjellige fra Min-Heaps og hvordan vi kan bruke prioriterte køer til å implementere Min-heaps.

Hva er en Min Heap?

En min-heap har egenskapen at hver node på nivå 'n' lagrer en verdi som er mindre enn eller lik verdien til dens underordnede på nivå 'n+1'. Fordi roten har en verdi mindre enn eller lik barna sine, som igjen har verdier mindre enn eller lik barna deres, lagrer roten minimum av alle verdier i treet.

Eksempel

Figur 1: En enkel min haug Legg merke til at det ikke er noe nødvendig forhold mellom verdien til en node og dens søsken i verken min-heapen eller max-heapen. For eksempel er det mulig at verdiene for alle noder i venstre undertre av roten er større enn verdiene for hver node i høyre undertre. Figur 2: Minste haug med venstre barnnoder > høyre barnnoder

Representasjon av Min Heap i Java

Den mest brukte datastrukturen for å representere en Min Heap er en enkel Array. Som nybegynner trenger du ikke å forveksle en "array" med en "min-heap". Du kan se på det som at verdiene til noder/elementer i en min-heap er lagret i en matrise . Akkurat som vi ikke har noen datastruktur for å lagre et " tre " i Java, og vi bygger en "node" for det, eller måten vi bruker "kart" for å lagre en " graf ". Figur 3: Array-representasjon av haugen i figur 2 Vi skal demonstrere hvordan du enkelt kan få tilgang til overordnede, høyre eller venstre underordnede noder ved å bruke følgende formler.

• La minHeap[] er en heltallsmatrise med rot ved indeksen " i = 0; ".
• minHeap[(i - 1) / 2] returnerer den overordnede noden.
• minHeap[(i * 2) + 2] returnerer høyre underordnet node.
• minHeap[(i * 2) + 1] returnerer den venstre underordnede noden.

Tatt i betraktning figur #2 gitt ovenfor, verdien av rot (foreldre) = 3, venstre underordnet node er 13 og høyre underordnet node = 7.

Implementering av Min Heap i Java - Bruke Arrays

La oss se på den grunnleggende implementeringen av Heaps ved å bruke array, med indeks som gjeldende posisjon til elementet som skal legges til, og størrelse som den totale størrelsen 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();
	}
}

Produksjon

Prioriterte køer

En prioritert kø er en spesiell type kø der hvert element er knyttet til en prioritet og plasseres i henhold til dens prioritet. For en enklere implementering av min heap bruker vi PriorityQueue-klassen java.util.PriorityQueue levert av Java. Hvis de gitte elementene skal sorteres/plasseres i en prioritet, brukes en Priority Queue. En Priority Queue er forskjellig fra en enkel Queue fordi standardkøene følger First-In-First-Out ( FIFO )-algoritmen, men noen ganger må elementene i køen behandles i henhold til prioritet, det er derfor Priority Queue er designet. Når du legger til elementer i en prioritert kø, bygges en min haug som standard.

Felles operasjoner

Før vi går videre til implementeringen her er noen vanlige operasjoner i java.util.PriorityQueue som du trenger å vite.

• add(int element) setter inn det angitte elementet i en prioritetskø.
• remove(int element) fjerner en enkelt forekomst av det spesifiserte elementet fra denne køen, hvis den er til stede.
• peek() henter, men fjerner ikke, hodet til denne køen, eller returnerer null hvis køen er tom.
• poll() henter og fjerner hodet på denne køen, eller returnerer null hvis denne køen er tom.
• contains() returnerer "true" hvis denne køen inneholder det spesifiserte elementet.
• size() returnerer antall elementer i denne prioriterte køen/minheapen.

Implementering av Min Heap i Java ved hjelp av prioriterte køer

Her er hvordan du kan implementere en min haug ved å bruke prioritert køklasse 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);
	}
}

Produksjon

Konklusjon

Min-hauger er mye brukt for å hente det minste elementet i en pool av elementer i konstant tid. Det er mange andre applikasjoner av denne datastrukturen, men du kan velge hvilken som helst metode for å implementere dette. Unødvendig å si at du må øve med tålmodighet for å bli god på det. Så la oss få musklene i gang og komme i gang!