Java の最小ヒープと例

始める前に、バイナリ ツリー について理解していることを前提とします(バイナリ ツリーでは、各ノードは、左側のサブツリーのすべてのキーよりも大きく、右側のサブツリーのすべてのキーよりも小さいキーを格納します)。一方、バイナリ ヒープは 、最小ヒープまたは最大ヒープの順序付けプロパティを満たす完全なバイナリ ツリーです。。これらの概念に慣れていない場合は、前提条件としてこれらを理解することをお勧めします。多くの初心者プログラマーは、ヒープ、最小ヒープ、優先キューの概念に苦労することがあります。この記事では、ヒープと最小ヒープの違いと、優先キューを使用して最小ヒープを実装する方法を詳しく説明します。

最小ヒープとは何ですか?

最小ヒープには、レベル「n」のすべてのノードがレベル「n+1」の子の値以下の値を格納するという特性があります。ルートはその子以下の値を持ち、ルートもその子以下の値を持つため、ルートはツリー内のすべての値の最小値を格納します。

例

図 1: 単純な最小ヒープ 最小ヒープまたは最大ヒープのいずれかで、ノードの値とその兄弟の値の間には必要な関係がないことに注意してください。たとえば、ルートの左側のサブツリーのすべてのノードの値が、右側のサブツリーのすべてのノードの値よりも大きい可能性があります。 図 2: 左の子ノード > 右の子ノードの最小ヒープ

Java での最小ヒープの表現

最小ヒープを表すために最も一般的に使用されるデータ構造は、単純な配列です。初心者は「配列」と「最小ヒープ」を混同する必要はありません。これは、最小ヒープのノード/要素の値が配列に格納されていると見ることができます。Java には「ツリー」を保存するためのデータ構造がなく、そのために「ノード」を構築するのと同じように、または「グラフ」を保存するために「マップ」を使用する方法と同じです。 図 3: 図 2 のヒープの配列表現 次の式を使用して、親、右または左の子ノードに簡単にアクセスする方法を示します。

• minHeap[] をインデックス「i = 0」にルートを持つ整数配列とします。”。
• minHeap[(i - 1) / 2] は親ノードを返します。
• minHeap[(i * 2) + 2] は、右側の子ノードを返します。
• minHeap[(i * 2) + 1] は、左側の子ノードを返します。

上記の図 2 を考慮すると、ルート (親) の値 = 3、左の子ノードは 13、右の子ノード = 7 となります。

Java での最小ヒープの実装 - 配列の使用

配列を使用したヒープの基本的な実装を見てみましょう。インデックスは追加する要素の現在位置、サイズは配列の合計サイズです。

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

出力

優先キュー

優先順位キューは、各要素が優先順位に関連付けられ、その優先順位に従って配置される特殊なタイプのキューです。最小ヒープを簡単に実装するには、Java が提供する PriorityQueue クラスjava.util.PriorityQueueを使用します。指定された要素が優先順位に基づいて並べ替えられたり、配置されたりする必要がある場合は、優先順位キューが使用されます。標準キューは先入れ先出し ( FIFO ) アルゴリズムに従っているため、優先キューは単純なキューとは異なりますが、場合によっては優先度に従ってキューの要素を処理する必要があるため、優先キューが設計されています。優先キューに要素を追加すると、デフォルトで最小ヒープが構築されます。

共通の操作

実装に進む前に、知っておく必要があるjava.util.PriorityQueueの一般的な操作をいくつか説明します。

• add(int element) は、指定された要素を優先キューに挿入します。
• Remove(int element) は、指定された要素の単一インスタンスをこのキューから削除します (存在する場合)。
• Peak()は、このキューの先頭を取得しますが、削除はしません。キューが空の場合は null を返します。
• poll() は、このキューの先頭を取得して削除します。このキューが空の場合は null を返します。
• contains() は、このキューに指定された要素が含まれている場合に「true」を返します。
• size() は、この優先キュー/ミニヒープ内の要素の数を返します。

優先キューを使用した Java での最小ヒープの実装

ここでは、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);
	}
}

出力

結論

最小ヒープは、要素のプール内の最小要素を一定時間で取得するために広く使用されています。このデータ構造の応用例は他にもたくさんありますが、これを実装するには任意の方法を選択できます。言うまでもなく、上達するには忍耐強く練習する必要があります。さあ、筋肉を動かして仕事に取り組みましょう！