힙에 새로운 데이터를 추가하거나 제거할 때 힙의 규칙을 지켜야 합니다.
최대 힙이면 부모 노드가 자식 노드보다 커야 하고
최소 힙은 자식 노드가 부모 노드보다 커야 합니다.
노드 추가
- 비어있는 공간에 노드를 추가합니다.
- 부모 노드보다 큰 숫자인지 확인하고 만약 그렇다면 두 노드를 바꿉니다. (trickle up)
trickle up
각 노드에는 위와 같이 숫자가 붙어있습니다.
예를 들어 3번노드의 자식 노드는 7과 8입니다.
즉 루트가 0인경우 모든 관계는 다음과 같이 성립할 수 있습니다.
자식노드 = 부모노드 x 2 + 1, 부모노드 x 2 + 2
반대로 자식 노드를 가지고 부모 노드를 알아 낼 수 있습니다.
부모노드 = floor(자식노드 - 1)/2
위와 같은 이진 힙을 코드로 구현하기위해선 배열을 사용할 수 있습니다.
배열의 각 인덱스에 노드의 값을 채우는 방법으로 코드를 작성해보겠습니다.
int lastposition; // 어디까지 요소를 넣었는지 기록
E[] array = (E[]) new Object[size];
public void add(E obj){
array[++lastposition] = obj; // 1. 노드 추가. (현재노드에 +1을 해준다.)
trickleup(lastposition); // 2. 요소를 추가할땐 trickle up과정이 필수.
}
public void swap(int from, int to){
E tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
public void trickleup(int position){
if (position == 0)
return; // 루트에 도달하면 종료.
int parent = (int) Math.floor((position-1)/2) // 현재위치로 부모노드 계산.
if (((Comparable<E>) array[position]).compareTo(array.parent)>0) {
swap(position, parent); // 부모노드가 자식노드를 비교하고 자리를 바꿈.
trickleup(parent); // 부모노드를 가지고 루트에 도달할때 까지 trickle up.
}
}배열은 실제 들어갈 요소의 개수보다 큰 배열이어야합니다.
lastposition 라는 전역변수는 요소가 어디까지 차 있는지 기록합니다.
힙에 요소를 추가할 때는 추가할 위치의 부모노드의 숫자와 비교를 하고,
부모노드보다 큰 경우 부모노드와 추가할 노드의 자리를 바꿔야합니다.
이 과정을 trinkle up이라고 합니다.
즉 요소를 추가할때는 trinkle up과정을 거쳐야합니다.
요소가 추가되었다면 lastposition 에 현재 위치를 알려줘야합니다.
현재위치를 알게되면 위에서 설명한대로 부모노드를 계산할 수 있게됩니다.
부모노드를 계산하면서 루트까지 도달하게되면 add가 완료됩니다.
루트 제거
- 루트를 제거합니다.
- 트리의 마지막 요소를 루트에 넣어줍니다.
- 루트에서 시작하여 두 자식 중 큰 노드와 바꿔주어 힙의 규칙을 만족하게 합니다. (trickle down)
무언가를 제거할 때 힙에서는 항상 루트를 제거해야 합니다
trickle down
요소를 제거하기 위해서는 무조건 루트를 제거하고 마지막 요소를 루트에 채워넣은 후, 자식노드오 비교해가면서 자리를 찾아가는 것을 trickle down라고 합니다.
trickle down을 사용해 루트 제거 과정은 다음과 같습니다.
자식노드의 위치를 가지고 자식 노드를 계산합니다.
전체 배열의 길이보다 계산한 자식노드의 숫자가 크면 trickle down이 멈추게 됩니다.
다만 현재노드의 자식노드가 1개만 있는 경우를 생각해야합니다.
public E remove(){ E tmp = array[0]; swap(0, lastposition--); // 루트와 마지막 노드를 바꿔주고 lastposition을 줄여 배열에서 제거합니다. trickleDown(0); return tmp; }루트의 값을 tmp라는 새로운 배열에 저장해 두겠습니다.
루트와 마지막 노드의 위치를 바꿔주고 배열은 하나 감소시켜 루트의 값을 배열에서 제외합니다.
그리고 0번째 노드인 루트를 lastposition와 위치를 바꿔주면서 하나 감소시켜주겠습니다.
이어서 루트에서부터
trickleDown을 반복하고 저장해 놓은 tmp를 반환합니다.
trickleDown()
trickleDown 메소드를 만들때 발생할 수 있는 예외상황을 고려해 다음과 같은 코드를 작성할 수 있습니다.
public void trickleDown(int parent){
int left = 2*parent + 1;
int right = 2*parent + 2;
// 마지막 노드와 왼쪽 자식이 같고 왼쪽 자식노드가 부모노드의 숫자보다 큰 경우
if (left==lastposition && (((Comparable<E>)array[parent]).compareTo(array[left])<0){
swap(parent, left) // 왼쪽 자식노드와 부모노드의 자리 교체
return;
}
// 마지막 노드와 오른쪽 자식이 같고 오른쪽 자식노드가 부모노드의 숫자보다 큰 경우
if (right==lastposition && (((Comparable<E>)array[parent]).compareTo(array[right])<0){
swap(parent, right) // 오른쪽 자식노드와 부모노드의 자리 교체
return;
}
// 부모가 클 때는 마지막이니까 바로 종료.
if (left >= lastposition || right >= lastposition)
return;
// 오른쪽자식과 왼쪽 자식 비교
// 왼쪽 자식이 클 때
if (array[left] > array[right] && array[parent] < array[left]) {
swap(parent, left);
trickleDown(left);
}
// 오른쪽 자식이 클 때
else if (array[parent] < array[right]){
swap(parent, right);
trickleDown(right);
}
}