힙(Heap)이란 ?
힙은 완전 이진트리 형태로 최대, 최소 값을 빠르게 찾아내는데 유용한 자료구조이다.
힙은 중복 값을 허용하며, 부모 - 자식 간 정렬은 보장하나 형제간의 정렬은 보장하지 않는다. (반 정렬 상태)
최소 힙( Min Heap)
최소 힙은 부모 노드의 Key가 자식 노드의 Key보다 작거나 같은 완전 이진트리이다.
최소 힙 - 삽입
- 트리의 가장 끝 위치에 데이터 삽입
- 부모 노드와 키 비교한 후 부모 보다 작을 경우 부모와 자리 교체 (반복)
최소 힙 - 삭제
- 최상위 노드 반환 및 삭제
- 가장 마지막 위치의 노드를 최상위 노드로 위치 시킴
- 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체 (반복)
최소 힙 - 구현
기본 구조
ArrayList<Integer> heap;
MinHeap() {
this.heap = new ArrayList<>();
this.heap.add(0);
}
ArrayList로 데이터를 관리해주고 생성자 호출시 0번 인덱스 자리에는 더미 데이터를 넣어준다.
삽입
public void insert(int data) {
heap.add(data);
int cur = heap.size() - 1; // 삽입한 데이터의 index
while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {
int parentVal = heap.get(cur / 2);
heap.set(cur / 2, data);
heap.set(cur, parentVal);
cur /= 2;
}
}
데이터를 힙의 가장 마지막에 삽입하고, 부모가 존재하고 부모보다 작을 경우 위치를 교체해준다.인덱스를 교체한 부모의 인덱스를 바꿔주고 루프를 반복한다.
삭제
public Integer delete() {
if (heap.size() == 1) {
System.out.println("Heap is empty!");
return null;
}
int target = heap.get(1); // 최상의 노드
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int cur = 1;
while (true) {
int leftIdx = cur * 2;
int rightIdx = cur * 2 + 1;
int targetIdx = -1;
if (rightIdx < heap.size()) {
targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
} else if (leftIdx < heap.size()) {
targetIdx = leftIdx;
} else {
break;
}
if (heap.get(cur) < heap.get(targetIdx)) {
break;
} else {
int parentVal = heap.get(cur);
heap.set(cur, heap.get(targetIdx));
heap.set(targetIdx, parentVal);
cur = targetIdx;
}
}
return target;
}
최상위 노드를 반환할 변수에 담아주고, 제일 마지막 데이터를 최상위로 옮겨준다.
우측 자식 노드가 존재 할 경우, 자식 노드가 둘 다 존재한다는 뜻이므로, 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 작은 자식 노드 (같을 경우 오른쪽 자식 노드)의 인덱스를 왼쪽 자식 노드만 존재 할 경우 왼쪽 자식 노드의 인덱스를 target 인덱스에 담아주고 자식이 더 작을 경우 자리를 바꿔준다. 그리고 target 인덱스로 인덱스를 바꿔주고 루프를 반복한다.
최종 코드
import java.util.ArrayList;
class MinHeap {
ArrayList<Integer> heap;
MinHeap() {
this.heap = new ArrayList<>();
this.heap.add(0);
}
public void insert(int data) {
heap.add(data);
int cur = heap.size() - 1; // 삽입한 데이터의 index
while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {
int parentVal = heap.get(cur / 2);
heap.set(cur / 2, data);
heap.set(cur, parentVal);
cur /= 2;
}
}
public Integer delete() {
if (heap.size() == 1) {
System.out.println("Heap is empty!");
return null;
}
int target = heap.get(1); // 최상의 노드
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int cur = 1;
while (true) {
int leftIdx = cur * 2;
int rightIdx = cur * 2 + 1;
int targetIdx = -1;
if (rightIdx < heap.size()) {
targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
} else if (leftIdx < heap.size()) {
targetIdx = leftIdx;
} else {
break;
}
if (heap.get(cur) < heap.get(targetIdx)) {
break;
} else {
int parentVal = heap.get(cur);
heap.set(cur, heap.get(targetIdx));
heap.set(targetIdx, parentVal);
cur = targetIdx;
}
}
return target;
}
public void printTree() {
for (int i = 1; i < this.heap.size(); i++) {
System.out.print(this.heap.get(i) + " ");
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.insert(1);
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(4);
minHeap.insert(6);
minHeap.insert(3);
minHeap.insert(5);
minHeap.insert(2);
minHeap.printTree();
System.out.println(minHeap.delete());
minHeap.printTree();
}
}
최대 힙( Max Heap)
최대 힙은 부모 노드의 Key가 자식 노드의 Key보다 크거나 같은 완전 이진트리이다.
최대 힙 - 삽입
- 트리의 가장 끝 위치에 데이터 삽입
- 부모 노드와 키 비교한 후 부모 보다 클 경우 부모와 자리 교체 (반복)
최대 힙 - 삭제
- 최상위 노드 반환 및 삭제
- 가장 마지막 위치의 노드를 최상위 노드로 위치 시킴
- 자식 노드 중 큰 값과 비교 후 부모 노드가 더 작으면 자리 교체 (반복)
'자료구조 > 비선형 자료구조' 카테고리의 다른 글
| [Java] 비선형 자료구조 - 트리 (0) | 2024.03.04 |
|---|