Java에서 최대 힙 데이터 구조 구현
최대 힙은 노드 값이 자식 값보다 크거나 같은 완전한 이진 트리입니다. Max Heap 데이터 구조는 힙 정렬을 사용하여 데이터를 정렬하는 데 유용합니다.
이 튜토리얼에서는 Java에서 처음부터 최대 힙을 구현하기 위해 알아야 할 모든 것을 다룰 것입니다.
Java에서 최대 힙 데이터 구조 구현
배열을 사용하여 힙을 나타냅니다. 힙은 완전한 이진 트리이므로 공간 낭비가 없습니다.
예를 들어 다음과 같은 힙을 생각해 봅시다.
배열 표현은 다음과 같습니다.
최대 힙 선언은 다음과 같이 수행됩니다.
static class MaxHeap {
private int[] Heap; // array
private int size;
private int maxsize;
public MaxHeap(int size) {
this.maxsize = size;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MAX_VALUE;
}
힙은 최대 힙을 저장하는 배열입니다. 생성자는 크기를 가져오고 0번째 요소를 무한대로 사용하여 배열을 초기화합니다. 인덱스 1에서 힙을 시작합니다.
1. 노드의 부모 가져오기
힙을 배열로 저장하므로 노드의 부모를 가져오는 것이 더 쉬워집니다.
위치 i에 있는 요소의 경우 부모의 위치는 다음과 같이 지정됩니다.
(i)/2
구현하는 동안 다음을 사용하여 부모를 얻을 수 있습니다.
private int parent(int pos) {
return pos / 2;
}
2. 노드의 자식 가져오기
위치 i에 있는 노드의 경우 자식은 다음 공식으로 제공됩니다.
왼쪽 자식:
(2*i)
오른쪽 자식 :
(2*i)+ 1
참고: 이것은 힙이 인덱스 1에서 시작하는 경우에 해당합니다. 힙이 위치 0에서 시작하는 경우 값은 각각 왼쪽 및 오른쪽 자식에 대해 (2*i) +1 및 (2*i) +2입니다. .
코드에서 다음과 같이 구현합니다.
private int leftChild(int pos) {
return (2 * pos) ;
}
private int rightChild(int pos) {
return (2 * pos) + 1;
}
3. 새로 삽입된 요소를 힙화
요소를 힙에 삽입한 후 힙 속성을 충족하지 못할 수 있습니다. 이 경우 힙의 위치를 조정하여 다시 힙으로 만들어야 합니다. 이 프로세스를 Heapifying이라고 합니다.
최대 힙의 요소를 힙화하려면 자식의 최대값을 찾아 현재 요소와 교체해야 합니다. 각 노드에서 힙 속성이 만족될 때까지 이 프로세스를 계속합니다.
heapify하기 위해 우리는 뿌리에서 잎으로 이동합니다. 따라서 이것은 Down Heapify라고도 합니다.
주목해야 할 또 다른 흥미로운 점은 리프가 아닌 노드에서만 다운 힙화를 수행한다는 것입니다.
down-heapify 함수의 코드는 다음과 같습니다.
private void downHeapify(int pos) {
//checking if the node is a leaf node
if (pos >= (size / 2) && pos <= size)
return;
//checking if a swap is needed
if (Heap[pos] < Heap[leftChild(pos)] ||
Heap[pos] < Heap[rightChild(pos)]) {
//replacing parent with maximum of left and right child
if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
//after swaping, heapify is called on the children
downHeapify(leftChild(pos));
} else {
swap(pos, rightChild(pos));
//after swaping, heapify is called on the children
downHeapify(rightChild(pos));
}
}
}
스왑 기능은 다음과 같습니다.
private void swap(int fpos, int spos) {
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
재귀 대신 while 루프를 사용하여 동일한 코드를 작성할 수도 있습니다.
down-heapify에서 우리는 부모에서 자식으로 이동했습니다. 상향식으로도 움직일 수 있습니다. 상향식 방식으로 이동할 때 노드를 부모 노드와 비교합니다. 이것을 업 히피파이라고 합니다.
up-heapify의 코드는 다음과 같습니다.
private void heapifyUp(int pos) {
int temp = Heap[pos];
while(pos>0 && temp > Heap[parent(pos)]){
Heap[pos] = Heap[parent(pos)];
pos = parent(pos);
}
Heap[pos] = temp;
}
재귀 대신 while 루프를 사용하여 heapify를 위한 코드를 작성했습니다.
4. 새 노드 삽입
배열 끝에 새 요소가 추가되고 힙 속성이 유지되도록 스왑이 수행됩니다.
삽입 알고리즘은 다음과 같습니다.
- 힙 크기 늘리기
- 힙(배열) 끝에 새 요소 유지
- 아래에서 위로 쌓기
삽입 코드는 다음과 같습니다.
public void insert(int element) {
Heap[++size] = element;
int current = size;
heapifyUp(current);
}
5. 노드 삭제/추출
힙에서 노드를 삭제/추출하려면 루트에서 요소를 삭제합니다. 루트는 항상 최대 요소를 제공합니다.
삭제 알고리즘은 다음과 같습니다.
- 첫 번째 요소를 변수에 복사합니다.
- 마지막 요소를 첫 번째 위치(루트)에 복사합니다.
- downHeapify()를 호출합니다.
삭제 코드는 다음과 같습니다.
public int extractMax() {
int max = Heap[1];
Heap[1] = Heap[size--];
downHeapify(1);
return max;
}
여기서 우리는 size--를 사용하여 힙의 크기를 줄입니다.
Java에서 최대 힙 구현 완료
Max Heap의 전체 Java 구현은 다음과 같습니다.
package com.JournalDev;
public class Main {
static class MaxHeap {
private int[] Heap;
private int size;
private int maxsize;
public MaxHeap(int size) {
this.maxsize = size;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MAX_VALUE;
}
private int parent(int pos) {
return pos / 2;
}
private int leftChild(int pos) {
return (2 * pos) ;
}
private int rightChild(int pos) {
return (2 * pos) + 1;
}
private void swap(int fpos, int spos) {
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
private void downHeapify(int pos) {
if (pos >= (size / 2) && pos <= size)
return;
if (Heap[pos] < Heap[leftChild(pos)] ||
Heap[pos] < Heap[rightChild(pos)]) {
if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
downHeapify(leftChild(pos));
} else {
swap(pos, rightChild(pos));
downHeapify(rightChild(pos));
}
}
}
private void heapifyUp(int pos) {
int temp = Heap[pos];
while(pos>0 && temp > Heap[parent(pos)]){
Heap[pos] = Heap[parent(pos)];
pos = parent(pos);
}
Heap[pos] = temp;
}
public void insert(int element) {
Heap[++size] = element;
int current = size;
heapifyUp(current);
}
public void print() {
for (int i = 1; i <= size / 2; i++) {
System.out.print(+ Heap[i] + ": L- " +
Heap[2 * i] + " R- " + Heap[2 * i + 1]);
System.out.println();
}
}
public int extractMax() {
int max = Heap[1];
Heap[1] = Heap[size--];
downHeapify(1);
return max;
}
}
public static void main(String[] arg)
{
MaxHeap maxHeap = new MaxHeap(15);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(2);
maxHeap.insert(5);
maxHeap.insert(13);
maxHeap.insert(6);
maxHeap.insert(17);
maxHeap.print();
System.out.println("The max is " + maxHeap.extractMax());
}
}
Output :
17: L- 5 R- 13
5: L- 1 R- 4
13: L- 2 R- 6
The max is 17
결론
이 튜토리얼은 Java의 최대 힙 데이터 구조에 관한 것입니다.