Min Heap w Javie z przykładami

Zanim zaczniemy, zakładamy, że wiesz o drzewie binarnym (w drzewie binarnym każdy węzeł przechowuje klucz większy niż wszystkie klucze w jego lewym poddrzewie i mniejszy niż wszystkie klucze w jego prawym poddrzewie ) . Podczas gdy sterta binarna jest kompletnym drzewem binarnym, które spełnia właściwość porządkowania min-heap lub max-heap. Jeśli nie znasz tych pojęć, zalecamy ich zrozumienie jako warunek wstępny. Wielu początkujących programistów może zmagać się z koncepcją stert, stert minimalnych i kolejek priorytetowych. W tym poście przyjrzymy się dokładniej, czym sterty różnią się od kopców minimalnych i jak możemy wykorzystać kolejki priorytetowe do zaimplementowania stert minimalnych.

Co to jest sterta minimalna?

Sterta min ma tę właściwość, że każdy węzeł na poziomie „n” przechowuje wartość mniejszą lub równą wartości swoich dzieci na poziomie „n+1”. Ponieważ korzeń ma wartość mniejszą lub równą swoim dzieciom, które z kolei mają wartości mniejsze lub równe ich dzieciom, korzeń przechowuje minimum wszystkich wartości w drzewie.

Przykład

Rysunek 1: Prosta sterta min Należy zauważyć, że nie ma koniecznego związku między wartością węzła a wartością jego rodzeństwa ani w stercie min, ani w stercie max. Na przykład, możliwe jest, że wartości dla wszystkich węzłów w lewym poddrzewie korzenia są większe niż wartości dla każdego węzła prawego poddrzewa. Rysunek 2: Min sterta z lewymi węzłami potomnymi > prawymi węzłami potomnymi

Reprezentacja Min Heap w Javie

Najczęściej używaną strukturą danych do reprezentowania Min Heap jest prosta tablica. Jako początkujący nie musisz mylić „tablicy” z „min-heap”. Możesz spojrzeć na to tak, jak wartości węzłów/elementów min-heap są przechowywane w tablicy . Tak jak nie mamy żadnej struktury danych do przechowywania „ drzewa ” w Javie i budujemy dla niego „węzeł” lub sposób, w jaki używamy „mapy” do przechowywania „wykresu ” . Rysunek 3: Tablicowa reprezentacja sterty na rysunku 2 Zademonstrujemy, w jaki sposób można łatwo uzyskać dostęp do węzłów nadrzędnych, prawych lub lewych węzłów potomnych za pomocą następujących formuł.

• Niech minHeap[] będzie tablicą całkowitą z pierwiastkiem w indeksie „ i = 0; ”.
• minHeap[(i - 1) / 2] zwraca węzeł nadrzędny.
• minHeap[(i * 2) + 2] zwraca prawy węzeł potomny.
• minHeap[(i * 2) + 1] zwraca lewy węzeł podrzędny.

Biorąc pod uwagę rysunek nr 2 podany powyżej, wartość pierwiastka (rodzica) = 3, lewy węzeł potomny to 13, a prawy węzeł potomny = 7.

Implementacja Min Heap w Javie - Wykorzystanie tablic

Przyjrzyjmy się podstawowej implementacji Heaps przy użyciu tablicy, z indeksem jako bieżącą pozycją dodawanego elementu i rozmiarem jako całkowitym rozmiarem tablicy.

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();
	}
}

Wyjście

Kolejki priorytetowe

Kolejka priorytetowa to specjalny rodzaj kolejki, w której każdy element jest powiązany z priorytetem i jest umieszczany zgodnie z jego priorytetem. Dla łatwiejszej implementacji sterty min używamy klasy PriorityQueue java.util.PriorityQueue dostarczanej przez Javę. Jeżeli dane elementy mają być posortowane/umieszczone w priorytecie to stosowana jest Kolejka Priorytetowa. Kolejka priorytetowa różni się od prostej kolejki, ponieważ standardowe kolejki są zgodne z algorytmem FIFO (First-In-First-Out ), ale czasami elementy kolejki muszą być przetwarzane zgodnie z priorytetem, dlatego zaprojektowano kolejkę priorytetową. Podczas dodawania elementów do kolejki priorytetowej domyślnie tworzona jest sterta min.

Wspólne operacje

Zanim przejdziemy do implementacji, oto kilka typowych operacji w java.util.PriorityQueue , które musisz znać.

• add(int element) wstawia określony element do kolejki priorytetowej.
• remove(int element) usuwa pojedynczą instancję określonego elementu z tej kolejki, jeśli jest obecna.
• peek() pobiera, ale nie usuwa nagłówka tej kolejki lub zwraca wartość null, jeśli kolejka jest pusta.
• poll() pobiera i usuwa nagłówek tej kolejki lub zwraca wartość null, jeśli ta kolejka jest pusta.
• zawiera() zwraca „true”, jeśli ta kolejka zawiera określony element.
• size() zwraca liczbę elementów w tej kolejce priorytetowej/minheap.

Implementacja Min Heap w Javie z wykorzystaniem kolejek priorytetowych

Oto jak możesz zaimplementować min stertę przy użyciu klasy kolejki priorytetowej przez 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);
	}
}

Wyjście

Wniosek

Kopce min są szeroko stosowane do pobierania najmniejszego elementu z puli elementów w stałym czasie. Istnieje wiele innych zastosowań tej struktury danych, jednak możesz wybrać dowolną metodę jej implementacji. Nie trzeba dodawać, że musisz ćwiczyć z cierpliwością, aby stać się w tym dobrym. Ruszmy zatem nasze mięśnie i do dzieła!