힙으로 우선순위 유지하지

힙은 트리 자료 구조 중 하나로 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다.
힙의 기능을 제대로 파악하려면 우선순위 큐에 대해서 알고 있어야 한다.

우선순위 큐

우선순위 큐는 삭제와 접근에 있어 전형적인 큐와 흡사하나 삽입에 있어 정렬된 배열과 비슷한 리스트다. 즉 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입 할 때는 데이터를 늘 특정 순서대로 정렬 시킨다.

[1,3,4,5]가 우선순위 큐에 들어 있다고 가정한다. 이 때 우선 순위 큐에 2를 삽입하면, [1,2,3,4,5]이 된다.

우선순위 큐는 추상 데이터 타입의 한 예다. 우선순위 큐를 간단하게 구현하려면 정렬된 배열을 이용하면 된다. 즉 배열을 사용하되 다음과 같은 제약을 가진다.

• 데이터를 삽입할 때 적절한 순서를 유지한다.
• 데이터는 배열 끝에서만 삭제한다(배열 끝이 큐의 앞).

우선순위 큐의 주요 연산은 삭제와 삽입이다. 배열의 맨 끝이 큐의 앞 이므로 정렬된 배열에서 맨 끝 데이터를 삭제하면 쉬프트가 발생하지 않는다. 따라서 삭제 연산은 O(1)이다.
하지만 삽입은 다르다. 정렬된 배열에 새로운 데이터를 삽입하려면 원소 N개를 모두 확인해야 하고, 앞 쪽에 데이터를 삽입해도 쉬프트가 발생하므로, O(N) 시간 복잡도를 가진다.
따라서 삽입 연산은 O(N)이다.

정렬된 배열 보다 우선순위 큐에 더욱 효율적인 자료 구조가 있다. 그게 바로 힙이다.

힙

힙 또한 종료가 다양하다. 여기서는 이진 힙에 대해서 알아보겠다.
이진 힙에는 최대 힙과 최쇠 힙이라는 두 종류가 있다.

힙은 다음과 같은 조건을 따른다.

• 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야한다. 이 조건을 힙 규칙이라 부른다.
• 트리는 완전해야 한다.

힙 조건

힙 조건이란 각 노드의 값이 그 노드의 모든 자손 노드보다 커야 한다는 뜻이다.

이진 탐색 트리에서는 오른쪽 자손이 부모 노드보다 커야 했지만, 힙에서 노드는 그 노드의 모든 자손보다 크다. 이진 탐색 트리로는 힙을 만들 수 없다.

정 반대로 각 노드가 자손보다 작은 값을 갖도록 힙을 구성할 수도 있다. 이런 힙을 최소 힙이라고 부른다. 두 힙은 힙 조건만 반대일 뿐 그 밖에 모든 면에서 동일하

88이라는 부모 노드가 존재 할 때 자식 노드는 88을 넘어서는 값을 가져서는 안된다.

완전 트리

완전 트리는 빠진 노드 없이 노드가 완전히 채워진 트리다.

트리의 각 레벨을 왼쪽부터 오른쪽으로 읽었을 때 모든 자리마다 노드가 있어야 한다.
단, 마지막 레벨은 예외로 한다. 이 때 빈자리의 오른쪽으로 어떤 노드도 없어야 한다.

즉 힙에 새로운 레벨이이 생겼을 때 왼쪽 노드부터 오른쪽 노드로 차근 차근 값이 채워져야 한다.

힙 속성

힙은 자손이 조상보다 클 수 없다는 순서가 있지만, 이것만으로는 왼쪽 자손을 탐색해야 할지 오른쪽 자손을 탐색해야 할지 정할 수 없다. 따라서 힙은 이진 탐색 트리에 비해 약한 정렬 weakly ordered이라고 말한다.

힙의 최댓값은 항상 루트 노드이다. 우선순위 큐에서는 항상 가장 큰 우선순위를 갖는 값에 접근하므로, 힙을 사용했다면 루트 노드가 가장 높은 우선 순위를 갖는 항목에 해당한다.

힙의 주요 연산은 삽입과 삭제다. 검색은 모든 노드를 검색해야 하므로 대개 구현하지 않는다. 읽기 연산은 선택적으로 있을 수 있다.

힙에는 마지막 노드라는 용어가 있는데, 바닥 줄에서 가장 오른쪽에 있는 노드를 뜻한다.

힙 삽입

삽입은 다음과 같은 알고리즘을 수행한다.
1. 새 값을 포함하는 노드를 생성하고 바닥 레벨의 가장 오른쪽 노드 옆에 삽입한다. 즉 이 값이 힙의 마지막 노드가 된다.
2. 이어서 새로 사입한 노드와 그 부모 노드를 비교한다.
3. 새 노드가 부모 노드보다 크면 새 노드와 그 부모 노드를 스왑한다.
4. 새 노드보다 큰 부모 노드를 만날 때까지 3단계를 반복하며 새 노드를 힙 위로 올린다.

새 노드를 힙 위로 올리는 과정을 노드를 위로 트리클링 trickling한다고 표현한다.
힙 삽입의 효율성은 O(logN) 이다.
노드가 N개인 이진 트리는 약 logN개의 줄을 갖는데, 새 값을 꼭대기 줄 까지 트리클링해야하는 최악의 경우 최대 logN 단계가 걸린다.

마지막 노드 탐색

근본적으로 힙에서 검색하는 것이 불가능하듯, 힙의 마지막 노드도 모든 노드를 검사하지 않고는 효율적으로 찾을 수 없다.

그렇다면 어떻게 힙에서 다음으로 노드가 들어 갈 자릴 찾을까???

이 문제를 마지막 노드 문제라고 부른다.

힙 삭제

힙의 루트 노드를 삭제하는 알고리즘은 다음과 같다.

1. 마지막 노드를 루트 노드 자리로 옮긴다. 결과적으로 원래 루트 노드는 삭제된다.
2. 루트 노드를 적절한 자리까지 아래로 트리클링한다.

트리클링 알고리즘은 다음과 같다. 트링클링 하는 노드 == 트리클 노드

1. 트리클 노드의 두 자식을 확인해 어느 쪽이 더 큰지 본다.
2. 트리클 노드가 두 자식 노드 중 큰 노드보다 작으면 큰 노드와 트리클 노드를 스왑한다.
3. 트리클 노드에 그 노드보다 큰 자식이 없을 때까지 1,2 단계를 반복한다.

즉 힙의 루트 노드만 삭제된다.

힙에서 삭제하려면 루트부터 시작해 logN개 레벨을 거쳐 노드를 트링클해야 하므로 사입과 마찬가지로 시간 복자도는 O(logN)이다.

힙 대 정렬된 배열

다음 표는 정렬된 배열과 힙을 나란히 비교한다.

	정렬된 배열	힙
삽입	O(N)	O(logN)
삭제	O(1)	O(logN)

정렬된 배열은 삽입에 잇어 힙보다 느리지만 삭제에 있어 힙보다 빠른다. 하지만 O(1) 엄청나게 빠르긴해도 O(logN) 역시 매우 빠르다. 이에 비해 O(N)은 느리다.

	정렬된 배열	힙
삽입	느림	매우빠름
삭제	엄청나게 빠름	매우빠름

엄청 빠르고 떄로는 느린 자료구조 보다는 일관되게 매우 빠른 자료 구조를 사용하는 편이 낫다. 우선 순위 큐는 일반적을 삭제와 삽입을 거의 비슷한 비율로 수행한다. 따라서 정렬된 배열이 아닌 힙을 사용한다.

다시 살펴보는 마지막 노드 문제

삽입과 삭제일 때 마지막 노드가 필요한 이유는 마지막 노드가 아니라면 힙이 불완전해지기 때문이다. 마지막 노드를 찾지 않고 힙을 계속 삽입한다고 생각해보자. 계속해서 작은 값을 삽입 하면서 왼쪽으로만 하위 노드가 늘어난다면 힙의 균형은 사리진다.
즉, 힙을 균형잡힌 상태로 유지하기 위해 마지막 노드가 필요하다.

균형이 중요한 이유는 O(logN) 안에 연산이 가능하기 때문이다. 한쪽으로만 자손이 있는 불균형 힙이라면 순회에 O(N)이 걸린다.

배열로 힙 구현하기

class Heap {
private ArrayList arrayList;
private Integer newNodeIndex;
private int largerChildIndex;
private Integer leftChildIndex;
private Integer rightChildIndex;
public Heap(){
this.arrayList = new ArrayList();
}
public T rootNode(){
return arrayList.get(0);
}
public T lastNode(){
return arrayList.get(arrayList.size() - 1);
}
public Integer leftChild(Integer index){
if (index2 + 1 > arrayList.size() - 1) return null;
return (index 2) + 1;
}
public Integer rightChild(Integer index){
if (index2 + 2 > arrayList.size() - 1) return null;
return (index 2) + 2;
}
public Integer parentIndex(Integer index){
return (index - 1) / 2;
}
public void insert(T value){
//데이터를 배열 끝에 삽입해 마지막 노드로 만든다.
this.arrayList.add(value);
// 새로 삽입한 노드의 인덱스를 저장한다.
this.newNodeIndex = arrayList.size() - 1;
// 위로 트리클링하는 알고리즘을 실행한다. 새 노드가 루트 자리에 없고, 부모 노드보다 크면
while (newNodeIndex > 0 && (Integer) arrayList.get(newNodeIndex) > (Integer) arrayList.get(parentIndex(newNodeIndex))){
// 새 노드와 부모 노드를 스왑한다.
swap(arrayList.get(parentIndex(newNodeIndex)),arrayList.get(newNodeIndex));
// 새 노드의 인덱스를 업데이트 한다.
newNodeIndex = parentIndex(newNodeIndex);
}
}
public void delete(){
// 힙에서는 루트 노드만 삭제하므로 배여렝서 마지막 노드를 팝해 루트 노드로 넣는다.
arrayList.set(0,arrayList.remove(arrayList.size() - 1));
// 트리클 노드의 현재 인덱스를 기록한다.
int trickleNodeIndex = 0;
// 아래로 트리클링하는 알고리즘 실행. 트리클 노드에 자기보다 큰 자식이 있으면 루프를 실행.
while (hasGreaterChild(trickleNodeIndex)){
//더 큰 자식의 인덱스를 변수해 저장한다.
largerChildIndex = calculateChild(trickleNodeIndex);
//트리클 노드와 더 큰 자식을 스왑한다.
T temp = arrayList.get(trickleNodeIndex);
arrayList.set(trickleNodeIndex,arrayList.get(largerChildIndex));
arrayList.set(largerChildIndex, temp);
// 트리클 노드의 새 인덱스를 업데이트 한다.
trickleNodeIndex = largerChildIndex;
}
return;
}
public Boolean hasGreaterChild(int index){
// 인덱스에 있는 노드에 왼쪽 자식이나 오른쪽 자식이 있는지, 어느 한 자식이라도 인덱스에 있는 노브도다 큰지 확인
leftChildIndex = leftChild(index);
if (leftChildIndex != null && (Integer) arrayList.get(leftChildIndex) > (Integer) arrayList.get(index)) return true;
rightChildIndex = rightChild(index);
if (rightChildIndex != null && (Integer) arrayList.get(rightChildIndex) > (Integer) arrayList.get(index)) return true;
return false;
}
public int calculateChild(int index){
// 오른쪽 자식이 없으면
if (arrayList.get(rightChild(index)) == null) return leftChild(index);
if ((Integer) arrayList.get(rightChild(index)) > (Integer) arrayList.get(leftChild(index)))
return rightChild(index);
else
return leftChild(index);
}
public void swap(T value1, T value2){
T temp = arrayList.get(parentIndex(newNodeIndex));
arrayList.set(parentIndex(newNodeIndex),arrayList.get(newNodeIndex));
arrayList.set(newNodeIndex, temp);
return;
}
public void print(){
System.out.println(arrayList);
}
}

대안 구현

배열을 써서 힙을 구현했으나 연결 리스트로도 구현할 수 있었다. 이렇게 구현하면 2진수를 활용하는 다른 방법으로 마지막 노드 문제를 해결한다. 배열을 쓴 이유는 더 널리 쓰이는 방식이기 때문이다.

모든 이진 트리는 배열로 구현할 수 있다. 하지만 힙은 마지막 노드를 쉽게 찾을 수 있다는 점에서 배열로 구현하면 특히 유리하다.

우선순위 큐로 쓰이는 힙

힙은 가장 높은 우선순위의 항목이 항상 루트 노드에 있으니 우선순위 큐를 구현하는데 딱 어울린다.
힙은 삽입과 삭제를 할 때마다 우선순위에 따라 값을 루트 노드에 정렬하며, 이 과정이 모두 O(logN)이다.

힙의 약한 정렬이 우선순위 큐를 구현하는데 굉장한 장점으로 작용했다.
힙은 최댓값에 항상 접근할 수 있을 만큼은 정렬되어 있다.
완벽하게 정렬할 필요가 없으니 새 값을 O(logN)시간에 삽입할 수 있다.

마무리

다양한 종류의 문제를 최적화하는 데 다양한 종류의 트리가 쓰일 수 있다.
이진 탐색 트리는 삽입 비용을 최소화하며 빠르게 검색할 수 있고, 힙은 우선순위 큐를 만드는 완벽한 도구이다.