Min Heap در جاوا با مثال

قبل از شروع، فرض بر این است که شما در مورد یک درخت باینری می دانید (در یک درخت باینری، هر گره یک کلید بزرگتر از همه کلیدهای زیردرخت سمت چپ خود و کمتر از همه کلیدهای زیردرخت سمت راست خود را ذخیره می کند ) . در حالی که، یک Heap باینری یک درخت باینری کامل است که ویژگی سفارش min-heap یا max-heap را برآورده می کند . اگر با این مفاهیم آشنا نیستید، به شما توصیه می کنیم که این مفاهیم را به عنوان پیش نیاز درک کنید. بسیاری از برنامه نویسان تازه کار می توانند با مفهوم Heaps، Min Heaps و Priority Queues مبارزه کنند. در این پست ما یک شیرجه عمیق انجام می دهیم تا ببینیم که heap ها چقدر با Min-Heaps متفاوت هستند و چگونه می توانیم از صف های اولویت برای پیاده سازی Min Heaps استفاده کنیم.

Min Heap چیست؟

min-heap این ویژگی را دارد که هر گره در سطح 'n' مقداری را ذخیره می کند که کمتر یا برابر با فرزندان خود در سطح 'n+1' است. از آنجایی که ریشه مقداری کمتر یا مساوی با فرزندان خود دارد، که به نوبه خود مقادیر کمتر یا مساوی با فرزندان خود دارند، ریشه حداقل همه مقادیر را در درخت ذخیره می کند.

مثال

شکل 1: یک پشته کوچک ساده توجه داشته باشید که هیچ رابطه ضروری بین مقدار یک گره و همتای آن در min-heap یا max-heap وجود ندارد. به عنوان مثال، ممکن است مقادیر تمام گره‌ها در زیردرخت سمت چپ ریشه بیشتر از مقادیر هر گره زیردرخت سمت راست باشد. شکل 2: حداقل توده با گره های فرزند چپ > گره های فرزند راست

نمایش Min Heap در جاوا

متداول‌ترین ساختار داده‌ای که برای نمایش Min Heap استفاده می‌شود، یک آرایه ساده است. به عنوان یک مبتدی، نیازی نیست که "آرایه" را با "min-heap" اشتباه بگیرید. می توانید به آن نگاه کنید که مقادیر گره ها / عناصر یک min-heap در یک آرایه ذخیره می شوند . همانطور که ما هیچ ساختار داده ای برای ذخیره یک " درخت " در جاوا نداریم و یک "گره" برای آن می سازیم، یا روشی که از "نقشه" برای ذخیره " گراف " استفاده می کنیم. شکل 3: نمایش آرایه Heap در شکل 2 ما می خواهیم نشان دهیم که چگونه می توانید با استفاده از فرمول های زیر به گره های والد، راست یا چپ فرزند دسترسی داشته باشید.

• اجازه دهید minHeap[] یک آرایه عدد صحیح با ریشه در شاخص “ i = 0; ".
• minHeap[(i - 1) / 2] گره والد را برمی گرداند.
• minHeap[(i * 2) + 2] گره فرزند سمت راست را برمی گرداند.
• minHeap[(i * 2) + 1] گره فرزند سمت چپ را برمی گرداند.

با توجه به شکل شماره 2 داده شده در بالا، مقدار ریشه (والد) = 3، گره فرزند چپ 13 و گره فرزند راست = 7 است.

پیاده سازی Min Heap در جاوا - با استفاده از آرایه ها

بیایید به پیاده سازی اولیه 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();
	}
}

خروجی

صف های اولویت دار

صف اولویت نوع خاصی از صف است که در آن هر عنصر با یک اولویت همراه است و بر اساس اولویت خود قرار می گیرد. برای پیاده‌سازی آسان‌تر min heap، از کلاس PriorityQueue java.util.PriorityQueue که توسط جاوا ارائه شده است استفاده می‌کنیم. اگر قرار باشد عناصر داده شده در یک اولویت مرتب شوند/قرار گرفته شوند، از یک صف اولویت استفاده می شود. یک صف اولویت با یک صف ساده متفاوت است زیرا صف های استاندارد از الگوریتم First-In-First-Out ( FIFO ) پیروی می کنند، اما گاهی اوقات عناصر صف باید بر اساس اولویت پردازش شوند، به همین دلیل است که صف اولویت طراحی می شود. وقتی عناصری را به صف اولویت اضافه می‌کنید، به‌طور پیش‌فرض یک پشته کوچک ساخته می‌شود.

عملیات مشترک

قبل از اینکه به پیاده سازی بپردازیم، در اینجا چند عملیات رایج در java.util.PriorityQueue وجود دارد که باید بدانید.

• add(int element) عنصر مشخص شده را در صف اولویت قرار می دهد.
• remove(int element) یک نمونه از عنصر مشخص شده را در صورت وجود از این صف حذف می کند.
• peek() سر این صف را بازیابی می کند، اما حذف نمی کند، یا اگر صف خالی باشد، null را برمی گرداند.
• poll() سر این صف را بازیابی و حذف می کند یا اگر این صف خالی باشد null را برمی گرداند.
• contain() "true" را برمی گرداند اگر این صف حاوی عنصر مشخص شده باشد.
• size() تعداد عناصر موجود در این صف اولویت/minheap را برمی گرداند.

پیاده سازی Min Heap در جاوا با استفاده از صف های اولویت

در اینجا نحوه پیاده سازی min heap با استفاده از کلاس صف اولویت توسط جاوا آمده است.

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

خروجی

نتیجه

Min heaps به طور گسترده ای برای بازیابی کوچکترین عنصر در مجموعه ای از عناصر در زمان ثابت استفاده می شود. بسیاری از کاربردهای دیگر از این ساختار داده وجود دارد، با این حال شما می توانید هر روشی را برای اجرای آن انتخاب کنید. نیازی به گفتن نیست که باید با صبر و حوصله تمرین کنید تا در این کار خوب شوید. پس بیایید ماهیچه هایمان را به حرکت در آوریم و دست به کار شویم!