Java에서 최소 힙 구현
최소 힙은 각 내부 노드가 자식 값보다 작거나 같은 힙입니다. 다음 항목에서 라이브러리를 사용하거나 사용하지 않고 최소 힙을 구현하는 방법을 살펴보겠습니다.
Java에서 라이브러리를 사용하지 않고 최소 힙 구현
이 예에서는 라이브러리를 사용하지 않고 구현된 것을 볼 수 있습니다. 여기에서 세 개의 인스턴스 변수를 생성하는 JavaMinHeap 클래스를 만듭니다. HeapArray는 힙의 모든 값을 유지하는 int 유형 배열이고, size는 힙의 크기이고, maxSize는 힙의 크기를 저장합니다. HeapArray의 최대 크기입니다. 또한 int 유형의 static 변수 FRONT를 만들고 1로 초기화합니다.
생성자에서 매개변수로 maxSize를 가져와 인스턴스 변수 maxSize에 저장합니다. size는 0으로, HeapArray는 maxSize + 1 크기의 int 배열로 초기화합니다. HeapArray의 첫 번째 인덱스에 Integer의 최소값을 저장합니다.
이제 힙에서 작업을 수행하는 메서드를 만듭니다. parent() 함수는 position을 매개변수로 사용하고 노드의 전달된 위치의 부모를 반환합니다. 그런 다음 매개변수로 받은 위치의 왼쪽 자식을 반환하는 leftChild()를 만듭니다. (2 * position) + 1 노드 값을 반환하는 rightChild()를 사용하는 오른쪽 자식도 마찬가지입니다.
isLeaf()는 노드가 리프 노드인지 여부를 확인합니다. 즉, 자식이 있음을 의미합니다. swapNodes()는 노드의 위치 fpos 값을 spos 위치로 바꾸는 메소드입니다. 메소드에서 temp 변수를 생성하여 초기화하고 HeapArray의 fpos 위치를 초기화하고 HeapArray의 spos 값을 HeapArray[fpos]에 저장합니다. 이제 temp 값을 HeapArray[spos]에 저장합니다.
convertToMinHeap()은 매개변수로 받은 위치가 리프인지 아닌지를 isLeaf를 사용하여 확인하고, 그렇지 않은 경우 HeapArray 위치의 현재 값이 왼쪽 자식이나 오른쪽 자식보다 큰지 확인합니다. 그런 다음 왼쪽 자식이 오른쪽 자식보다 작은지 확인하고, 그렇다면 swapNodes()를 사용하여 노드를 교환하고 position과 왼쪽 자식을 position에 전달합니다. 다시 convertToMinHeap()을 사용하여 받은 왼쪽 자식을 최소 힙으로 변환합니다.
insert()를 사용하여 최소 힙에 값을 삽입합니다. insert()에서 배열이 maxSize에 도달하면 삽입하지 않고 반환합니다. 그렇지 않은 경우 ++size에서 위치를 얻고 수신된 요소를 HeapArray[++size]에 삽입합니다. 현재에 크기를 넣습니다. 현재 위치에 있는 요소가 상위 요소보다 작은 경우 루프를 만들고 노드를 교체합니다.
최소 힙을 인쇄하기 위해 printheap()을 만들고 부모가 ith 위치에 있고 왼쪽 자식이 2 * i 위치에 있고 오른쪽 자식이 다음과 같은 HeapArray를 반복합니다. 2 * i + 1 위치에서. main() 함수에서 insert()를 사용하여 힙에 요소를 삽입합니다.
public class JavaMinHeap {
private final int[] HeapArray;
private int size;
private final int maxsize;
private static final int FRONT = 1;
public JavaMinHeap(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
HeapArray = new int[this.maxsize + 1];
HeapArray[0] = Integer.MIN_VALUE;
}
private int parent(int position) {
return position / 2;
}
private int leftChild(int position) {
return (2 * position);
}
private int rightChild(int position) {
return (2 * position) + 1;
}
private boolean isLeaf(int position) {
if (position >= (size / 2) && position <= size) {
return true;
}
return false;
}
private void swapNodes(int fpos, int spos) {
int temp;
temp = HeapArray[fpos];
HeapArray[fpos] = HeapArray[spos];
HeapArray[spos] = temp;
}
private void convertToMinHeap(int position) {
if (!isLeaf(position)) {
if (HeapArray[position] > HeapArray[leftChild(position)]
|| HeapArray[position] > HeapArray[rightChild(position)]) {
if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
swapNodes(position, leftChild(position));
convertToMinHeap(leftChild(position));
} else {
swapNodes(position, rightChild(position));
convertToMinHeap(rightChild(position));
}
}
}
}
public void insert(int element) {
if (size >= maxsize) {
return;
}
HeapArray[++size] = element;
int current = size;
while (HeapArray[current] < HeapArray[parent(current)]) {
swapNodes(current, parent(current));
current = parent(current);
}
}
public void printHeap() {
for (int i = 1; i <= size / 2; i++) {
System.out.println("PARENT : " + HeapArray[i]);
System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);
System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
System.out.println();
}
}
public static void main(String[] arg) {
System.out.println("The Min Heap is ");
JavaMinHeap minHeap = new JavaMinHeap(10);
minHeap.insert(10);
minHeap.insert(2);
minHeap.insert(7);
minHeap.insert(15);
minHeap.insert(90);
minHeap.insert(19);
minHeap.insert(8);
minHeap.insert(22);
minHeap.insert(9);
minHeap.printHeap();
}
}
출력:
The Min Heap is
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7
PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90
PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8
PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15
Java에서 PriorityQueue를 사용한 최소 힙 구현
이 프로그램에서는 최대 및 최소 힙을 생성하는 데 사용되는 PriorityQueue를 사용합니다. PriorityQueue는 요소를 큐에 삽입하는 add()와 같은 다중을 제공하고, peek()은 큐의 헤드를 가져와 제거하고, poll()은 큐의 헤드를 검색하지만 제거하지는 않습니다. contains()는 지정된 요소가 대기열인지 확인합니다. remove()는 지정된 요소를 제거합니다.
PriorityQueue의 모든 기능을 결합하여 최소 힙 작업을 생성하고 수행합니다. 먼저 new PriorityQueue()를 사용하여 Integer 유형의 빈 priorityQueue 객체를 만듭니다. 그런 다음 add() 메서드를 사용하여 요소를 추가합니다. 대기열 헤드를 인쇄하고 제거하기 위해 10을 인쇄하는 priorityQueue.peek()를 호출합니다. 그런 다음 향상된 for를 사용하여 대기열의 모든 요소를 인쇄합니다. 이제 10을 인쇄하고 제거하는 poll()을 호출합니다. 그런 다음 대기열에서 요소를 제거합니다. 요소가 대기열에 있는지 확인하기 위해 boolean을 반환하는 contains()를 사용합니다. 마지막으로 나머지 값을 인쇄하기 위해 toArray()를 사용하여 대기열을 배열로 변환합니다.
import java.util.*;
public class JavaMinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(15);
priorityQueue.add(25);
priorityQueue.add(200);
System.out.println("The head value using peek(): " + priorityQueue.peek());
System.out.println("The queue elements: ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.poll();
System.out.println("After removing the head element using poll(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
priorityQueue.remove(25);
System.out.println("After removing 25 with remove(): ");
for (Integer integer : priorityQueue) System.out.println(integer);
boolean b = priorityQueue.contains(15);
System.out.println("Check if priorityQueue contains 15 using contains(): " + b);
Object[] arr = priorityQueue.toArray();
System.out.println("Values in array: ");
for (Object o : arr) System.out.println("Value: " + o.toString());
}
}
출력:
The head value using peek(): 10
The queue elements:
10
15
25
200
After removing the head element using poll():
15
200
25
After removing 25 with remove():
15
200
Check if priorityQueue contains 15 using contains(): true
Values in array:
Value: 15
Value: 200
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn