Heap - JavaScript
Algorithm
2023년 11월 4일
목차
📌 Heap 이란?
- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리
- 완전 이진트리 (Complete binary Tree) : 왼쪽부터 빈 공간 없이 채워나가는 이진트리
- 좌, 우 위치가 대소 관계를 반영하지 않는다. (층으로 대소 관계를 구분)
- 우선순위 큐 (Priority Queue)를 구현할 때 사용
- 우선순위 큐 : 큐의 기존 규칙이 FIFO가 아닌 일정한 규칙에 의해 먼저 나가는 숫자가 정해지는 것
📌 Heap 종류 (규칙)
- Min Heap (최소 힙) : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 힙
- Max Heap (최대 힙) : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙
📌 Push, PoP (삽입, 삭제)
9, 7, 5, 1, 3의 데이터가 heap 에 있다고 가정- MaxHeap 기준으로 설명
- 삽입, 삭제 후 Min/Max Heap으로 고치는 과정을 Heapify라고 함
push() ⇒ 부모노드와 비교후 swap
ex) push(11)
pop()
- 해당 위치에 힙의 마지막에 있는 노드를 위치 시킴
- 새로 들어온 노드와 children 노드들을 비교해서 그 중 큰 숫자와 swap
ex) pop(9)
📌 성질, 시간복잡도
위의 트리를 배열로 나타낸다면
let arr = [9, 7, 5, 1 ,3]
// 인덱스 0 1 2 3 4🔎 index 구하기
특정 노드에서 부모노드로 : **idx - 1 / 2** (결과가 소수일 경우 내림)
ex) 3일 경우 index → 4 이므로 4-1 / 2 = 1.5 ⇒ 1
부모 노드에서 left child로 : **2 * idx + 1**
ex) 7의 경우 index → 1 이므로 2*1 + 1 ⇒ 3
부모 노드에서 right child로 : 2 * idx + 2
ex) 7의 경우 index → 1 이므로 2*1 + 2 ⇒ 4
🕰️ 시간 복잡도
Root 노드에 접근하는 시간 (Max 값 or Min 값) : O(1)
Build Heap - 힙을 만드는데 필요한 시간 : O(N)
삽입, 삭제 : O(logN)
🛠 구현
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
swap(idx1, idx2){
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
return this.heap;
}
getParentIdx(childIdx){
return Math.floor((childIdx-1) / 2);
}
getLeftChildIdx(parentIdx){
return parentIdx*2 + 1;
}
getRightChildIdx(parentIdx){
return parentIdx*2 + 2;
}
heappop(){
const heapSize = this.size();
if (!heapSize) return null;
if (heapSize === 1) return this.heap.pop();
const value = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbledown();
return value;
}
heappush(value){
this.heap.push(value);
this.bubbleup();
return this.heap;
}
bubbleup() {
let child = this.size()-1;
let parent = this.getParentIdx(child);
while(this.heap[child] < this.heap[parent]){
this.swap(child, parent);
child = parent;
parent = this.getParentIdx(parent);
}
}
bubbledown() {
let parent = 0;
let leftChild = this.getLeftChildIdx(parent);
let rightChild = this.getRightChildIdx(parent);
while((leftChild <= this.size()-1 && this.heap[leftChild] < this.heap[parent]) || (rightChild <= this.size()-1 && this.heap[rightChild] < this.heap[parent])){
if (rightChild <= this.size()-1 && this.heap[leftChild] > this.heap[rightChild]){
this.swap(parent, rightChild);
parent = rightChild;
}else {
this.swap(parent, leftChild);
parent = leftChild;
}
leftChild = this.getLeftChildIdx(parent);
rightChild = this.getRightChildIdx(parent);
}
}
}