Min Heap in Java met voorbeelden

Voordat we beginnen, wordt ervan uitgegaan dat u iets weet over een binaire boom (in een binaire boom slaat elk knooppunt een sleutel op die groter is dan alle sleutels in zijn linker subboom en minder dan alle sleutels in zijn rechter subboom ) . Terwijl een binaire heap een complete binaire boom is die voldoet aan de eigenschap min-heap of max-heap ordening. Als u niet bekend bent met deze concepten, raden we u aan deze als eerste vereiste te begrijpen. Veel beginnende programmeurs kunnen worstelen met het concept van Heaps, Min Heaps en Priority Queues. In dit bericht gaan we dieper in op hoe heaps verschillen van Min-Heaps en hoe we Priority Queues kunnen gebruiken om Min Heaps te implementeren.

Wat is een min-heap?

Een min-heap heeft de eigenschap dat elk knooppunt op niveau 'n' een waarde opslaat die kleiner is dan of gelijk is aan die van zijn kinderen op niveau 'n+1'. Omdat de wortel een waarde heeft die kleiner is dan of gelijk is aan zijn kinderen, die op hun beurt waarden hebben die kleiner zijn dan of gelijk zijn aan hun kinderen, slaat de wortel het minimum van alle waarden op in de boom.

Voorbeeld

Figuur 1: Een eenvoudige min-heap Merk op dat er geen noodzakelijke relatie is tussen de waarde van een knooppunt en die van zijn broer of zus in de min-heap of de max-heap. Het is bijvoorbeeld mogelijk dat de waarden voor alle knooppunten in de linkersubboom van de wortel groter zijn dan de waarden voor elk knooppunt van de rechtersubboom. Afbeelding 2: min. heap met linker onderliggende knooppunten > rechter onderliggende knooppunten

Vertegenwoordiging van Min Heap op Java

De meest gebruikte datastructuur om een ​​Min Heap weer te geven is een eenvoudige Array. Als beginner hoef je een “array” niet te verwarren met een “min-heap”. Je kunt het zien als: de waarden van knooppunten / elementen van een min-heap worden opgeslagen in een array . Net zoals we geen datastructuur hebben om een ​​" boom " op te slaan in Java en we er een "node" voor bouwen, of de manier waarop we "kaart" gebruiken om een ​​" grafiek " op te slaan. Figuur 3: matrixweergave van de heap in figuur 2 We gaan demonstreren hoe u eenvoudig toegang kunt krijgen tot de bovenliggende, rechter of linker onderliggende knooppunten met behulp van de volgende formules.

• Laat minHeap[] een integer-array zijn met root op index “ i = 0; ”.
• minHeap[(i - 1) / 2] retourneert het bovenliggende knooppunt.
• minHeap[(i * 2) + 2] retourneert het rechter onderliggende knooppunt.
• minHeap[(i * 2) + 1] retourneert het linker onderliggende knooppunt.

Gezien de figuur # 2 die hierboven is gegeven, is de waarde van root (ouder) = 3, het linker kindknooppunt is 13 en het rechter kindknooppunt = 7.

Implementatie van Min Heap in Java - Arrays gebruiken

Laten we eens kijken naar de basisimplementatie van Heaps met behulp van array, met index als de huidige positie van het toe te voegen element en size als de totale grootte van de 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();
	}
}

Uitgang

Prioritaire wachtrijen

Een prioriteitswachtrij is een speciaal type wachtrij waarin elk element is gekoppeld aan een prioriteit en wordt geplaatst op basis van zijn prioriteit. Voor een eenvoudigere implementatie van min heap gebruiken we de PriorityQueue-klasse java.util.PriorityQueue van Java. Als de gegeven elementen in een prioriteit moeten worden gesorteerd/geplaatst, wordt een Priority Queue gebruikt. Een Priority Queue verschilt van een eenvoudige Queue omdat de standaardwachtrijen het First-In-First-Out ( FIFO )-algoritme volgen, maar soms moeten de elementen van de wachtrij worden verwerkt volgens de prioriteit, daarom is Priority Queue ontworpen. Wanneer u elementen toevoegt aan een prioriteitswachtrij, wordt standaard een minimale heap gebouwd.

Gemeenschappelijke operaties

Voordat we verder gaan met de implementatie, volgen hier enkele algemene bewerkingen in java.util.PriorityQueue die u moet kennen.

• add(int element) voegt het gespecificeerde element in een prioriteitswachtrij in.
• remove(int element) verwijdert een enkel exemplaar van het gespecificeerde element uit deze wachtrij, indien aanwezig.
• peek() haalt de kop van deze wachtrij op, maar verwijdert deze niet, of retourneert null als de wachtrij leeg is.
• poll() haalt de kop van deze wachtrij op en verwijdert deze, of retourneert null als deze wachtrij leeg is.
• bevat() retourneert "true" als deze wachtrij het opgegeven element bevat.
• size() retourneert het aantal elementen in deze prioriteitswachtrij/minheap.

Implementatie van Min Heap in Java met behulp van Priority Queues

Hier leest u hoe u een min-heap kunt implementeren met behulp van de prioriteitswachtrijklasse van 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);
	}
}

Uitgang

Conclusie

Min-heaps worden veel gebruikt om het kleinste element in een verzameling elementen in een constante tijd op te halen. Er zijn tal van andere toepassingen van deze gegevensstructuur, maar u kunt elke methode kiezen om dit te implementeren. Onnodig te zeggen dat je met geduld moet oefenen om er goed in te worden. Dus laten we onze spieren in beweging krijgen en aan het werk gaan!