Min Heap ב-Java עם דוגמאות

לפני שנתחיל, ההנחה היא שאתה יודע על עץ בינארי (בעץ בינארי, כל צומת מאחסן מפתח גדול יותר מכל המפתחות בתת-העץ השמאלי שלו ופחות מכל המפתחות בתת -העץ הימני שלו ) . בעוד, ערימה בינארית היא עץ בינארי שלם אשר עונה על תכונת הסדר המינימלית או הערימה המקסימלית . אם אינך מכיר את המושגים הללו, אנו ממליצים לך להבין אותם כתנאי מוקדם. מתכנתים מתחילים רבים יכולים להיאבק בקונספט של Heaps, Min Heaps ותורי עדיפות. בפוסט זה נצלול עמוק כדי לראות כיצד ערימות שונות מ-Min-Heaps וכיצד אנו יכולים להשתמש בתורי עדיפות כדי ליישם Min-Heaps.

מה זה Min Heap?

ל-min-heap יש את המאפיין שכל צומת ברמה 'n' מאחסן ערך הקטן או שווה לזה של הילדים שלו ברמה 'n+1'. מכיוון שלשורש יש ערך קטן או שווה לילדיו, שבתורם יש ערכים פחות או שווים לילדים שלהם, השורש אוגר את המינימום של כל הערכים בעץ.

דוגמא

איור 1: ערימה מינימלית פשוטה שים לב שאין קשר הכרחי בין הערך של צומת לזה של אחיו בערימה המינימלית או הערימה המקסימלית. לדוגמה, ייתכן שהערכים עבור כל הצמתים בתת-העץ השמאלי של השורש גדולים יותר מהערכים עבור כל צומת בתת-העץ הימני. איור 2: ערימה מינימלית עם צמתי צאצא שמאל > צמתי צאצא ימין

ייצוג של Min Heap ב-Java

מבנה הנתונים הנפוץ ביותר לייצוג Min Heap הוא מערך פשוט. בתור מתחיל אתה לא צריך לבלבל "מערך" עם "מיני-ערימה". אתה יכול להסתכל על זה בתור, הערכים של צמתים / אלמנטים של ערימה מינימלית מאוחסנים במערך . בדיוק כמו שאין לנו שום מבנה נתונים לאחסון " עץ " ב-Java ואנחנו בונים לו "צומת", או הדרך בה אנו משתמשים ב"מפה" לאחסון " גרף ". איור 3: ייצוג מערך של הערימה באיור 2 אנו הולכים להדגים כיצד אתה יכול פשוט לגשת לצמתים האב, הימני או השמאלי של הילד באמצעות הנוסחאות הבאות.

• תן minHeap[] הוא מערך שלמים עם שורש באינדקס " i = 0; ".
• minHeap[(i - 1) / 2] מחזירה את צומת האב.
• minHeap[(i * 2) + 2] מחזירה את הצומת הצאצא הימני.
• minHeap[(i * 2) + 1] מחזירה את צומת הצאצא השמאלי.

בהתחשב באיור מס' 2 המופיע למעלה, הערך של שורש (הורה) = 3, צומת צאצא שמאלי הוא 13 וצומת צאצא ימני = 7.

הטמעת Min Heap ב-Java - שימוש במערכים

בואו נסתכל על היישום הבסיסי של Heaps באמצעות מערך, עם אינדקס כמיקום הנוכחי של האלמנט שיש להוסיף, וגודל כגודל הכולל של המערך.

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

תְפוּקָה

תורי עדיפות

Priority Queue הוא סוג מיוחד של תור שבו כל אלמנט משויך לעדיפות וממוקם לפי העדיפות שלו. ליישום קל יותר של min heap, אנו משתמשים במחלקה PriorityQueue java.util.PriorityQueue שמסופקת על ידי Java. אם האלמנטים הנתונים אמורים להיות ממוינים/למקם בעדיפות אז נעשה שימוש בתור עדיפות. Priority Queue שונה מתור פשוט מכיוון שהתורים הסטנדרטיים עוקבים אחר האלגוריתם First-In-First-Out ( FIFO ), אבל לפעמים צריך לעבד את רכיבי התור לפי העדיפות, לכן תוכנן Priority Queue. כאשר אתה מוסיף אלמנטים לתור עדיפות, ערימה מינימלית נבנית כברירת מחדל.

פעולות נפוצות

לפני שנעבור ליישום הנה כמה פעולות נפוצות ב- java.util.PriorityQueue שאתה צריך לדעת.

• add(int element) מכניס את האלמנט שצוין בתור עדיפות.
• remove(int element) מסיר מופע בודד של הרכיב שצוין מהתור הזה, אם הוא קיים.
• peek() מאחזר, אך לא מסיר, את ראש התור הזה, או מחזיר null אם התור ריק.
• poll() מאחזר ומסיר את ראש התור הזה, או מחזיר null אם התור הזה ריק.
• contains() מחזירה "true" אם תור זה מכיל את האלמנט שצוין.
• size() מחזיר את מספר האלמנטים בתור העדיפות/minheap זה.

הטמעת Min Heap ב-Java באמצעות Priority Queues

הנה איך אתה יכול ליישם ערימה מינימלית באמצעות מחלקת תור עדיפות על ידי 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);
	}
}

תְפוּקָה

סיכום

ערימות דקות נמצאות בשימוש נרחב כדי לאחזר את האלמנט הקטן ביותר במאגר של אלמנטים בזמן קבוע. יש הרבה יישומים אחרים של מבנה הנתונים הזה, אולם אתה יכול לבחור כל שיטה ליישם זאת. מיותר לציין שצריך להתאמן בסבלנות כדי להצליח בזה. אז בואו נניע את השרירים שלנו ונתחיל לעבוד!