이진 탐색 트리 외의 다른 트리 종류도 많다. 그 중 하나가 힙이다.
힙은 데이터 세트에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다.
16.1 우선순위 큐
우선순위 큐는 삭제와 접근에 있어서는 전형적인 큐와 흡사하나, 삽입에 있어 정렬된 배열과 비슷한 리스트이다.
즉, 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되, 삽입할 때는 늘 특정 순서대로 정렬시킨다.
병원 응급실의 중증도 분류체계 관리 애플리케이션이 예이다. 응급실에서는 도착한 순서대로 진료를 하는 것이 아니라, 중증도를 따져 진료한다.
중증도가 심한 순서대로 치료(앞에서만 데이터에 접근하고 삭제)하고, 새로운 환자가 들어오면 중증도에 따라 적절한 순서를 매긴다(삽입할 때는 늘 특정 순서대로 정렬).
우선순위 큐는 추상 데이터 타입으로, 기초적인 다른 자료 구조로 구현할 수 있다. 정렬된 배열을 이용해서 간단하게 구현할 수 있다. 즉, 우선순위 큐는 다음과 같은 제약을 가한 배열이다.
- 데이터를 삽입할 때 항상 적절한 순서를 유지한다.
- 데이터는 배열 끝에서만 삭제한다(배열 끝이 우선순위 큐의 앞이다).
배열 끝에서 삭제하니 O(1)이다. 하지만 삽입에는 정렬을 위해 검색을 먼저 해야하니 O(N)이 걸린다. 항목이 많아지면 삽입에 지연이 발생할 수 있다.
우선순위 큐에서 정렬된 배열보다 효율적인 기반으로 쓰일 자료 구조가 힙이다.
16.2 힙
힙에는 여러 종류가 있으나 이진 힙을 주로 다룬다.
이진 힙은 특수한 종류의 이진 트리, 즉 각 노드에 최대 자식 노드가 둘인 트리다. 이진 힙에도 최대 힙과 최소 힙이라는 두 종류가 있으나 둘 간에 큰 차이는 없다. 일단 최대 힙부터 다룬다.
최대 힙은 다음의 조건을 따르는 이진 트리다.
- 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야 한다. 이 규칙을 힙 조건 heap condition이라고 한다.
- 트리는 완전해야 한다.
16.2.1 힙 조건
힙 조건이란 각 노드의 값이 그 노드의 모든 자손 노드보다 커야 한다는 뜻이다.
이진 탐색 트리에서는 오른쪽 자손이 부모 노드보다 커야 했지만, 힙에서 노드는 그 노드의 모든 자손보다 크다. 이진 탐색 트리로는 힙을 만들 수 없다.
정 반대로 각 노드가 자손보다 작은 값을 갖도록 힙을 구성할 수도 있다. 이런 힙을 최소 힙이라고 부른다. 두 힙은 힙 조건만 반대일 뿐 그 밖에 모든 면에서 동일하다.
16.2.2 완전 트리
완전 트리는 빠진 노드 없이 노드가 완전히 채워진 트리다.
트리의 각 레벨을 왼쪽부터 오른쪽으로 읽었을 때 모든 자리마다 노드가 있어야 한다.
단, 마지막 레벨은 예외로 한다. 이 때 빈자리의 오른쪽으로 어떤 노드도 없어야 한다.
16.3 힙 속성
힙은 자손이 조상보다 클 수 없다는 순서가 있지만, 이것만으로는 왼쪽 자손을 탐색해야 할지 오른쪽 자손을 탐색해야 할지 정할 수 없다. 따라서 힙은 이진 탐색 트리에 비해 약한 정렬 weakly ordered이라고 말한다.
힙의 최댓값은 항상 루트 노드이다. 우선순위 큐에서는 항상 가장 큰 우선순위를 갖는 값에 접근하므로, 힙을 사용했다면 루트 노드가 가장 높은 우선 순위를 갖는 항목에 해당한다.
힙의 주요 연산은 삽입과 삭제다. 검색은 모든 노드를 검색해야 하므로 대개 구현하지 않는다. 읽기 연산은 선택적으로 있을 수 있다.
힙에는 마지막 노드라는 용어가 있는데, 바닥 줄에서 가장 오른쪽에 있는 노드를 뜻한다.
16.4 힙 삽입
힙에 새 값을 삽입하려면 다음 알고리즘을 수행한다.
- 새 값을 포함하는 노드를 생성하고 마지막 노드 옆에 삽입한다. 즉, 이 값이 힙의 새로운 마지막 노드이다.
- 새로 삽입한 노드와 그 부모 노드를 비교한다.
- 새 노드가 부모 노드보다 크면 새 노드와 부모 노드를 스왑한다.
- 새 노드보다 큰 부모 노드를 만날 때까지 3단계를 반복하며 새 노드를 힙 위로 올린다.
새 노드를 힙 위로 올리는 과정을 노드를 위로 트리클링 trickling한다고 표현한다.
힙 삽입의 효율성은 O(logN) 이다.
노드가 N개인 이진 트리는 약 log₂N개의 줄을 갖는데, 새 값을 꼭대기 줄 까지 트리클링해야하는 최악의 경우 최대 log₂N 단계가 걸린다.
16.5 마지막 노드 탐색
근본적으로 힙에서 검색하는 것이 불가능하듯, 힙의 마지막 노드도 모든 노드를 검사하지 않고는 효율적으로 찾을 수 없다.
이 이슈를 '마지막 노드 문제'라고 해두고 삭제부터 살펴본다.
16.6 힙 삭제
힙에서 값을 삭제하려면 루트 노드만 삭제할 수 있다. 이는 우선순위 큐의 동작 방식과 일치한다.
힙의 루트 노드를 삭제하는 알고리즘은 다음과 같다.
- 마지막 노드를 루트 노드 자리로 옮긴다. 결과적으로 원래 루트 노드는 삭제된다.
- 마지막 노드가 루트 노드에 있으므로 힙 조건이 깨진 상태이다. 루트 노드를 적절한 자리까지 아래로 트리클링한다.
- 트리클링할 노드의 두 자식을 확인해 어느 쪽이 더 큰지 본다.
- 트리클링할 노드가 두 자식 노드 중 큰 노드보다 작으면 큰 노드와 트리클링할 노드를 스왑한다.
- 트리클링할 노드에 그 노드보다 큰 자식이 없을 때까지 1-2단계를 반복한다.
힙 삭제 역시 O(logN) 이다.
16.7 힙 대 정렬된 배열
정렬된 배열은 삽입에 O(N), 삭제에 O(1)이었고, 힙은 둘 다 O(logN)이었다.
즉, 힙은 정렬된 배열에 비해 삭제에서는 느리지만 삽입에 있어서는 빠르다.
O(1)이 엄청나게 빠르긴 하지만, O(logN) 역시 매우 빠르다. 하지만 O(N)은 느리다. 때로는 엄청 빠르고 때로는 느린 자료 구조보다는 일관되게 매우 빠른 자료 구조인 힙을 사용하는 편이 낫다.
우선순위 큐는 일반적으로 삽입과 삭제를 거의 비슷한 비율로 수행한다. 삽입과 삭제 중 한 연산이라도 느리면 우선순위 큐는 효율성이 떨어진다.
16.8 다시 살펴보는 마지막 노드 문제
삽입과 삭제일 때 마지막 노드가 필요한 이유는 마지막 노드가 아니라면 힙이 불완전해지기 때문이다. 즉, 힙을 균형잡힌 상태로 유지하기 위해 마지막 노드가 필요하다.
균형이 중요한 이유는 O(logN) 안에 연산이 가능하기 때문이다. 한쪽으로만 자손이 있는 불균형 힙이라면 순회에 O(N)이 걸린다.
16.9 배열로 힙 구현하기
마지막 노드 찾기는 힙 연산의 핵심이고, 효율적으로 찾아야 하므로 주로 배열을 사용해 힙을 구현한다.
힙 자체가 내부적으로 배열을 사용하는 추상 데이터 타입일 수 있다.
각 노드를 배열의 인덱스에 배열하는데는 특정한 패턴이 있다.
- 루트 노드는 항상 인덱스 0에 저장한다.
- 한 레벨 아래로 내려가 왼쪽에서 오른쪽 방향으로 진행하며 각 노드마다 배열의 다음 인덱스를 할당한다.
- 레벨 끝에 도달하면 다음 레벨로 내려가 같은 패턴을 반복한다.
이렇게 힙을 구현하면 마지막 노드는 항상 배열의 마지막 원소가 된다.
즉, 배열의 마지막 요소에 접근하면 마지막 노드를 찾을 수 있다. 새 노드를 삽입할 때도 배열 끝에 삽입하면 새 노드가 마지막 노드가 된다.
class Heap {
constructor() {
this.data = [];
}
rootNode() {
return this.data[0];
}
lastNode() {
return this.data[this.data.length - 1];
}
}빈 배열로 힙을 초기화 한다. rootNode 메서드는 배열의 첫 번째 항목을 반환하고, lastNode 메서드는 배열의 마지막 항목을 반환한다.
16.9.1 배열 기반 힙 순회
힙 삽입, 힙 삭제가 가능하려면 힙을 트리클링할 수 있어야 한다.
트리클링을 하려면 노드의 부모나 자식에 접근해서 힙을 순회할 수 있어야 한다.
16.9의 패턴으로 힙 노드에 인덱스를 할당하면 다음과 같은 힙 특성을 항상 만족한다.
- 어떤 노드의 왼쪽 자식을 찾으려면
(index * 2) + 1공식을 사용한다. - 어떤 노드의 오른쪽 자식을 찾으려면
(index * 2) + 2공식을 사용한다. - 어떤 노드의 부모를 찾으려면
(index - 1) / 2공식을 사용한다.- 이 때 소숫점 이하는 버린다.
노드의 인덱스를 넣어 해당 공식을 사용하면 자식 혹은 부모의 인덱스가 나온다.
leftChildIndex(index) {
return index * 2 + 1;
}
rightChildIndex(index) {
return index * 2 + 2;
}
parentIndex(index) {
return Math.floor((index - 1) / 2);
}16.9.2 코드 구현: 힙 삽입
insert(value) {
// value를 배열 끝에 삽입해 마지막 노드로 만든다.
this.data.push(value);
// 새로 삽입한 노드의 인덱스를 저장한다
let newNodeIndex = this.data.length - 1;
// 위로 트리클링하는 알고리즘
// 새 노드가 루트 자리에 없고 새 노드가 부모 노드보다 크면
while (
newNodeIndex > 0 &&
this.data[newNodeIndex] > this.data[this.parentIndex(newNodeIndex)]
) {
// 새 노드와 부모 노드를 스왑한다.
[this.data[this.parentIndex(newNodeIndex)], this.data[newNodeIndex]] = [
this.data[newNodeIndex],
this.data[this.parentIndex(newNodeIndex)],
];
// 새 노드의 인덱스를 업데이트한다.
newNodeIndex = this.parentIndex(newNodeIndex);
}
}새로 삽입할 값 value를 this.data 배열 끝에 추가해 마지막 노드로 만든다. 이 노드의 인덱스를 newNodeIndex에 저장한다.
이후 while 반복문을 사용해 새 노드를 위로 트리클링한다. 주된 조건은 새 노드가 부모 노드보다 클 때이다. 새 노드의 인덱스가 0보다 크다는 것은 새 노드가 루트 노드라는 것을 뜻한다.
반복문이 실행된다는 것은 새 노드가 부모보다 크다는 것이므로, 둘을 스왑하고 새 노드의 인덱스를 업데이트한다.
반복문이 실행되지 않는다면 새 노드가 부모보다 크지 않다는 것이므로 새 노드가 올바른 자리에 들어갔다는 뜻이다.
16.9.3 코드 구현: 힙 삭제
delete() {
// 힙에서는 루트 노드만 삭제하므로
// 배열에서 마지막 노드를 팝해 루트 노드로 넣는다.
this.data[0] = this.data.pop();
// 트리클링할 노드의 현재 인덱스를 기록한다.
let trickleNodeIndex = 0;
// 아래로 트리클링하는 알고리즘
// 트리클링할 노드에 자기보다 큰 자식이 있으면
while (this.hasGreaterChild(trickleNodeIndex)) {
// 더 큰 자식의 인덱스를 변수에 저장
const largerChildIndex = this.calculateLargerChildIndex(trickleNodeIndex);
// 트리클링할 노드와 더 큰 자식을 스왑한다.
[this.data[trickleNodeIndex], this.data[largerChildIndex]] = [
this.data[largerChildIndex],
this.data[trickleNodeIndex],
];
// 트리클 노드의 새 인덱스를 업테이트 한다.
trickleNodeIndex = largerChildIndex;
}
}
hasGreaterChild(index) {
// index에 있는 노드에 왼쪽 자식이나 오른쪽 자식이 있는지
// 어느 한 자식이라도 index에 있는 노드보다 큰지 확인
return (
(this.data[this.leftChildIndex(index)] &&
this.data[this.leftChildIndex(index)] > this.data[index]) ||
(this.data[this.rightChildIndex(index)] &&
this.data[this.rightChildIndex(index)] > this.data[index])
);
}
calculateLargerChildIndex(index) {
// 오른쪽 자식이 없으면
if (!this.data[this.rightChildIndex(index)]) {
// 왼쪽 자식의 인덱스 반환
return this.leftChildIndex(index);
}
// 오른쪽 자식의 값이 왼쪽 자식의 값보다 크면
if (
this.data[this.rightChildIndex(index)] >
this.data[this.leftChildIndex(index)]
) {
// 오른쪽 자식의 인덱스 반환
return this.rightChildIndex(index);
} else {
// 왼쪽 자식의 값이 오른쪽 자식의 값보다 크거나 같으면
// 왼쪽 자식의 인덱스 반환
return this.leftChildIndex(index);
}
}트리클링할 노드가 가진 자식이 자신보다 큰지를 판단하는 hasGreaterChild 메서드와 자신보다 큰 자식이 있다면 그 자식의 인덱스를 반환하는 calculateLargerChildIndex 메서드를 함께 만들었다.
delete 메서드에서는 먼저 마지막 값을 삭제해 첫 번째 값으로 넣는다.
이후 새 루트 노드를 아래로 트리클링하기 위해 인덱스를 저장한다. 처음에는 인덱스 0에 있으므로 0으로 초기화한다.
while 반복문으로 아래로 트리클링한다. 이 반복문은 트리클링할 노드에 그 노드보다 큰 자식이 있는 동안 실행된다.
트리클링할 노드의 자식 중 더 큰 자식의 인덱스를 구해 largerChildIndex에 저장하고, 트리클링할 노드와 더 큰 자식 노드를 스왑한다. 이후 트리클링할 노드의 새 인덱스를 업데이트한다.
16.9.4 대안 구현
배열을 써서 힙을 구현했으나 연결 리스트로도 구현할 수 있었다. 이렇게 구현하면 2진수를 활용하는 다른 방법으로 마지막 노드 문제를 해결한다. 배열을 쓴 이유는 더 널리 쓰이는 방식이기 때문이다.
모든 이진 트리는 배열로 구현할 수 있다. 하지만 힙은 마지막 노드를 쉽게 찾을 수 있다는 점에서 배열로 구현하면 특히 유리하다.
16.10 우선순위 큐로 쓰이는 힙
힙은 가장 높은 우선순위의 항목이 항상 루트 노드에 있으니 우선순위 큐를 구현하는데 딱 어울린다.
힙은 삽입과 삭제를 할 때마다 우선순위에 따라 값을 루트 노드에 정렬하며, 이 과정이 모두 O(logN)이다.
힙의 약한 정렬이 우선순위 큐를 구현하는데 굉장한 장점으로 작용했다.
힙은 최댓값에 항상 접근할 수 있을 만큼은 정렬되어 있다.
완벽하게 정렬할 필요가 없으니 새 값을 O(logN)시간에 삽입할 수 있다.
16.11 마무리
다양한 종류의 문제를 최적화하는 데 다양한 종류의 트리가 쓰일 수 있다.
이진 탐색 트리는 삽입 비용을 최소화하며 빠르게 검색할 수 있고, 힙은 우선순위 큐를 만드는 완벽한 도구이다.
