트리에 데이터가 들어가거나 삭제될 때 최대 최소값만 가장 위로 올라가는 구조이며 그 이외에는 정렬되어있지 않다. 이를 반정렬 상태라고 한다.
중복된 값이 들어갈 수 있다.
루트가 항상 최소가 되게 하는 힙을 최소 힙(min heap)이라고 하며 루트가 항상 최대가 되게 하는 힙을 최대 힙(max heap)이라고 한다.
힙의 구현
이번에 구현할 힙은 최소 힙으로 구현하며 다음과 같은 연산을 가진다.
데이터의 삽입
데이터의 삭제
힙의 요소 출력
힙은 완전 이진 트리의 특성을 가지기 때문에 배열로 손쉽게 구현이 가능하다.
기본적힌 힙의 구조는 다음과 같다.
import java.util.*;
// min Heap
class MyHeap{
ArrayList<Integer> heap;
MyHeap(){
heap = new ArrayList<>();
heap.add(-1);
}
public void add(int data){
}
public int remove(){
}
public void printTree(){
for (int i = 1; i < heap.size(); i++){
System.out.print(heap.get(i) + " ");
}
System.out.println();
}
}
힙의 자료 삽입
힙의 자료 삽입은 다음과 같이 이루어진다.
완전 이진 트리의 특성에 맞게 데이터를 삽입한다. 즉 좌에서 우로 데이터를 삽입한다.
이후 삽입한 위치부터 부모 노드와 값을 비교해 위치를 변경한다. 위치를 변경함으로서 힙의 부모 노드는 자식 노드보다 작아야 한다 라는 조건을 충족시키게 된다.
아래와 같은 트리에서 6을 삽입했다. 완전 이진 트리의 특성에 맞게 삽입한 것을 볼 수 있다.
최소 힙에서 노드의 삽입
이후 부모 노드는 자식 노드보다 작아야 한다는 원칙을 지키기 위해 부모 노드와 값을 비교한다.
여기서는 25와 값을 비교하며 25보다 작으므로 두 노드의 위치(값)을 바꾸게 된다.
위치가 바뀐 후의 힙
이제 다시 부모와 비교하며 부모보다 큰 위치가 생길 때 까지 위치를 이동한다.
완전히 이동이 끝난 최소 힙
이러면 최소 힙에서 노드의 삽입이 완료되었다.
이를 코드로 구현하면 아래와 같다.
public void add(int data){
heap.add(data);
int cur = heap.size() - 1;
// heap 에 들어간 데이터가 루트가 아니고 부모보다 내가 작은 동안 나는 위로 올라간다.
while(cur > 1 && heap.get(cur / 2) > heap.get(cur)){
int parentValue = heap.get(cur / 2);
// swap
heap.set(cur / 2, data);
heap.set(cur, parentValue);
// 이동했을 시 위치 갱신
cur /= 2;
}
}
완전 이진 트리 구조에서 어떤 인덱스가 있을 때 인덱스 / 2를 수행한 위치는 해당 노드의 부모 노드임을 기억하라
해당 사항만 인지하면 나머지는 위에서 설명한 그대로를 구현한 것에 불과하다.
힙에서 자료의 삭제
힙에서 자료를 삭제하는 방법은 아래와 같이 이루어진다.
루트에 존재하는 값을 반환하고 힙에서 가장 마지막에 삽입된 데이터를 루트에 넣는다.
이후 최소 힙에 맞도록 비교하며 데이터의 위치를 이동시킨다.
이때 좌측 자식만 있는경우, 두 자식이 존재하는 경우의 2가지 케이스가 있다.
좌측 자식만 존재하는 경우 좌측 자식쪽으로 데이터의 위치를 내려보낸다.
두 자식이 존재하는 경우 두 자식 중 더 작은 값을 가진 자식과 데이터를 비교하고 위치를 교환한다.
예시 트리
해당 힙에서 자료를 삭제해보자.6을 반환하고 마지막에 위치한 25를 루트로 올리게 된다.
위치 교환 직후의 힙
이제 부모 노드의 값이 자식 노드보다 작도록 위치를 재조정한다. 이때 25는 두 자식 10, 30이 있는데 이 경우 위에서 서술한 것 처럼 10과 30중 더 작은 값과 비교하게 된다. 즉 10과 비교하게 된다.
10이 25보다 작기 때문에 25와 10은 위치를 변경한다.
이후 내려간 위치에서 다시 자식과 비교를 수행한다. 두 자식이 있기 떄문에 15, 18 중 더 작은 값과 비교하게 되며 15가 더 작기 때문에 위치를 바꾸게 된다
이를 코드로 옮기면 다음과 같다.
public int remove(){
if (this.heap.size() == 1){
return -1;
}
int data = this.heap.get(1);
this.heap.set(1, heap.get(heap.size() - 1));
this.heap.remove(heap.size() - 1);
int cur = 1;
while(true){
int left = cur * 2;
int right = cur * 2 + 1;
int location = -1;
if (right < heap.size()){
location = heap.get(left) < heap.get(right) ? left : right;
} else if (left < heap.size()){
location = left;
} else{
break;
}
if (heap.get(cur) < heap.get(location)){
break;
} else{
int parentVal = heap.get(cur);
heap.set(cur, heap.get(location));
heap.set(location, parentVal);
cur = location;
}
}
return data;
}
정리
최소 힙은 자료의 삽입과 삭제에서 부모 노드는 자식 노드보다 그 크기가 작아야 한다 라는 원칙만을 지키면서 구현하면 어렵지 않다.
최대 힙은 크기 비교를 정 반대로만 하면 되므로 구현에 크게 어렵지 않을 것이다.
전체적인 코드는 다음과 같다.
import java.util.*;
// min Heap
class MyHeap{
ArrayList<Integer> heap;
MyHeap(){
heap = new ArrayList<>();
heap.add(-1);
}
public void add(int data){
heap.add(data);
int cur = heap.size() - 1;
// heap 에 들어간 데이터가 루트가 아니고 부모보다 내가 작은 동안 나는 위로 올라간다.
while(cur > 1 && heap.get(cur / 2) > heap.get(cur)){
int parentValue = heap.get(cur / 2);
// swap
heap.set(cur / 2, data);
heap.set(cur, parentValue);
// 이동했을 시 위치 갱신
cur /= 2;
}
}
public int remove(){
if (this.heap.size() == 1){
return -1;
}
int data = this.heap.get(1);
this.heap.set(1, heap.get(heap.size() - 1));
this.heap.remove(heap.size() - 1);
int cur = 1;
while(true){
int left = cur * 2;
int right = cur * 2 + 1;
int location = -1;
if (right < heap.size()){
location = heap.get(left) < heap.get(right) ? left : right;
} else if (left < heap.size()){
location = left;
} else{
break;
}
if (heap.get(cur) < heap.get(location)){
break;
} else{
int parentVal = heap.get(cur);
heap.set(cur, heap.get(location));
heap.set(location, parentVal);
cur = location;
}
}
return data;
}
public void printTree(){
for (int i = 1; i < heap.size(); i++){
System.out.print(heap.get(i) + " ");
}
System.out.println();
}
}
public class StudyCode {
public static void main(String[] args){
MyHeap heap = new MyHeap();
heap.add(10);
heap.add(25);
heap.add(24);
heap.add(13);
heap.add(7);
heap.printTree();
System.out.println(heap.remove());
System.out.println(heap.remove());
heap.printTree();
}
}
