힙은 완전 이진트리 기반의 자료구조로, 우선순위 큐를 구현하는데 사용된다.
트리 구조이기 때문에 삽입과 삭제에 O(logN)의 시간이 소요된다.
힙의 종류에는 최대힙, 최소힙이 있다.
힙을 통해 최댓값이나 최솟값을 찾는 연산을 빠르게 수행할 수 있다.
트리의 root 노드에 가장 큰 값이 위치해 있다.
부모노드가 자식노드 보다 항상 크거나 같은 값을 가진다.
트리의 root 노드에 가장 작은 값이 위치해 있다.
부모노드가 자신노드 보다 항상 작거나 같은 값을 가진다.
아무튼, 자바스크립트에서는 힙을 기본 라이브러리로 제공하지 않기에, 직접 구현해서 사용해야한다!
힙에서 부모 노드 - 자식 노드의 관계
- 왼쪽 자식 index = (부모 index) * 2
- 오른쪽 자식 index = (부모 index) * 2 + 1
- 부모 index = Math.floor(자식 index) / 2
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;
}
}