시작하기 전에 이진 트리 (이진 트리에서 각 노드는 왼쪽 하위 트리 의 모든 키보다 크고 오른쪽 하위 트리 의 모든 키보다 작은 키 를 저장함 ) 에 대해 알고 있다고 가정합니다 . 반면 이진 힙은 최소 힙 또는 최대 힙 순서 속성을 만족하는 완전한 이진 트리입니다.. 이러한 개념에 익숙하지 않은 경우 이러한 개념을 전제 조건으로 이해하는 것이 좋습니다. 많은 초보 프로그래머는 힙, 최소 힙 및 우선 순위 큐의 개념으로 어려움을 겪을 수 있습니다. 이 게시물에서는 힙이 Min-Heap과 어떻게 다른지, 우선 순위 큐를 사용하여 Min Heap을 구현하는 방법을 자세히 알아보겠습니다.
최소 힙이란 무엇입니까?
최소 힙은 '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();
}
}
산출
최소 힙: [3, 13, 7, 16, 21, 12, 9] 부모: 3 왼쪽: 13 오른쪽:7 부모: 13 왼쪽: 16 오른쪽:21 부모: 7 왼쪽: 12 오른쪽:9 최소값 is : 3 Min Heap is : [7, 13, 9, 16, 21, 12, 9] // 루트를 제거한 후 Parent : 7 Left : 13 Right :9 Parent : 13 Left : 16 Right :21 Parent : 9 왼쪽 : 12
우선순위 대기열
우선 순위 대기열은 각 요소가 우선 순위 와 연결되고 해당 우선 순위에 따라 배치되는 특별한 유형의 대기열입니다 . 최소 힙을 더 쉽게 구현하기 위해 Java에서 제공하는 PriorityQueue 클래스 java.util.PriorityQueue 를 사용합니다 . 주어진 요소가 우선 순위에 정렬/배치되어야 하는 경우 우선 순위 큐가 사용됩니다. 우선순위 대기열은 표준 대기열이 FIFO(First-In-First-Out ) 알고리즘을 따르기 때문에 단순한 대기열과 다릅니다. 그러나 때로는 대기열의 요소가 우선순위에 따라 처리되어야 하기 때문에 우선순위 대기열이 설계되었습니다. 우선순위 큐에 요소를 추가하면 기본적으로 최소 힙이 생성됩니다.
공통 작업
구현으로 이동하기 전에 알아야 할 java.util.PriorityQueue 의 몇 가지 일반적인 작업이 있습니다.
add(int 요소) 지정된 요소를 우선 순위 대기열에 삽입합니다.
remove(int element)는 지정된 요소가 있는 경우 이 대기열에서 단일 인스턴스를 제거합니다.
peek() 는 이 대기열의 헤드를 검색하지만 제거하지는 않습니다. 대기열이 비어 있으면 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);
}
}
최소 힙은 일정한 시간에 요소 풀에서 가장 작은 요소를 검색하는 데 널리 사용됩니다. 이 데이터 구조의 다른 응용 프로그램이 많이 있지만 이를 구현하는 방법을 선택할 수 있습니다. 잘하려면 인내심을 가지고 연습해야 한다는 것은 말할 필요도 없습니다. 이제 근육을 움직이고 일을 시작합시다!
GO TO FULL VERSION