Binary Heap (이진 힙)
완전 이진 트리(Complete Binary Tree)의 일종으로 여러 개의 값 중에 최대값 또는 최소값을 빠르게 찾을 수 있도록 하는 자료구조입니다.
완전 이진 트리(Complete Binary Tree)란?
마지막 레벨을 제외한 모든 노드가 차있는 상태이며, 마지막 레벨의 노드 중 왼쪽 노드가 채워져 있는 트리.
힙의 종류
힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 나뉘어집니다.
힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지하는데 최대힙의 경우 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨이 있어야 합니다.
즉 부모 노드의 값이 자식 노드의 값보다 커야하며, 부모 노드와 자식 노드 사이에는 대소 관계가 성립합니다. 반대로 최소힙의 경우에는 자식노드보다 부모 노드의 값이 작은 경우를 말합니다.
힙의 데이터 삽입
힙은 완전 이진 트리이기 때문에 삽입하는 노드를 왼쪽 최하단 노드부터 채우게 됩니다. [15, 10, 8] 값들을 순서대로 넣는다고 가정할 때 최대힙을 기준으로 설명하면,
- 왼쪽 최하단 노드에 15 삽입
- 15를 부모 노드로 둔 채 다시 왼쪽 최하단 노드에 10을 삽입한 뒤,
부모노드인 15와 비교 후 15보다 작으므로 기존 자리에 위치 - 왼쪽 최하단 노드는 이미 채워져 있으므로, 오른쪽 최하단 노드에 8 삽입
- 부모노드인 15와 비교 후, 작으므로 기존 자리에 위치
새로 삽입할 데이터의 값이 부모 노드보다 클 경우에는 부모 노드와 자식노드가 위치를 바꾸어가며 트리를 구성합니다.
- 왼쪽 최하단 노드에 20을 삽입
- 부모노드인 8과 비교하여 8보다 크므로 부모노드와 위치 변경 (현재는 최대힙을 만드는 과정이므로)
- 다시 부모노드인 15와 비교하여 15보다 크므로 위치 변경
힙의 데이터 삭제와 정렬
힙의 목표는 최대값과 최소값을 찾는 것입니다. 최대힙인지 또는 최소힙인지에 따라 루트 노드는 최대값 또는 최소값을 갖게 되며, 목표에 맞춰 가장 먼저 삭제됩니다.
그러므로 힙에서 최대값과 최소값을 탐색할 때의 시간복잡도는 O(1)입니다. 그러나 데이터가 삭제되면, 힙의 구조를 유지하기 위해 제거된 루트 노드를 대체할 다른 노드를 찾게되는데,
이 때 가장 마지막 노드를 루트 노드로 끌어 올려와서 다시 정렬하는 과정을 거치게 됩니다.
- 루트 노드가 삭제됐을 때, 가장 마지막에 생성된 노드 8을 루트 노드로 이동
- 루트 노드인 8보다 값이 큰 자식 노드가 있는지 비교
- 모든 자식 노드가 루트 노드의 값보다 클 경우 왼쪽 자식노드와 오른쪽 자식 노드를 비교하여 더 큰 자식 노드를 부모 노드의 위치와 변경
- 하나의 자식 노드만 부모 노드보다 클 경우 해당 노드를 부모 노드의 위치와 변경
- 위 사진의 경우 10, 15 둘 다 8보다 크므로 비교하여 더 큰 15를 부모 노드인 루트 노드 위치로 이동
즉 노드들이 각각의 부모와 자식 노드와 비교해가며 위치를 재설정하기 때문에 힙이 정렬될 때의 시간 복잡도는 O(logN)입니다.
힙의 구현
힙을 저장하는 표준 자료구조는 배열(Array)입니다. 쉽게 구현하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않고 루트 노드부터 1번으로 시작합니다. 그렇기 때문에 힙을 배열로 구현할 때에는 일정한 관계가 성립됩니다.
- 왼쪽 자식의 idx =
부모 idx * 2 - 오른쪽 자식의 idx =
(부모 idx * 2) + 1 - 부모 idx =
Math.floor(자식 idx / 2)
알고리즘 풀이에서 타 언어의 경우 힙을 기본 제공 해주는 경우가 많지만,
JS의 경우 기본적으로 제공해주는 Heap 함수가 없기 때문에 직접 만들어 사용해야 합니다.
아래는 최소힙을 만드는 로직을 JS로 구현한 예시입니다.
class MinHeap {
constructor() {
this.heap = [ null ];
}
size() {
return this.heap.length - 1;
}
getMin() {
return this.heap[1] ? this.heap[1] : null;
}
swap(a, b) {
[ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
}
heappush(value) {
this.heap.push(value);
let curIdx = this.heap.length - 1;
let parIdx = (curIdx / 2) >> 0;
while(curIdx > 1 && this.heap[parIdx] > this.heap[curIdx]) {
this.swap(parIdx, curIdx)
curIdx = parIdx;
parIdx = (curIdx / 2) >> 0;
}
}
heappop() {
const min = this.heap[1];
if(this.heap.length <= 2) this.heap = [ null ];
else this.heap[1] = this.heap.pop();
let curIdx = 1;
let leftIdx = curIdx * 2;
let rightIdx = curIdx * 2 + 1;
if(!this.heap[leftIdx]) return min;
if(!this.heap[rightIdx]) {
if(this.heap[leftIdx] < this.heap[curIdx]) {
this.swap(leftIdx, curIdx);
}
return min;
}
while(this.heap[leftIdx] < this.heap[curIdx] || this.heap[rightIdx] < this.heap[curIdx]) {
const minIdx = this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
this.swap(minIdx, curIdx);
curIdx = minIdx;
leftIdx = curIdx * 2;
rightIdx = curIdx * 2 + 1;
}
return min;
}
}