## 코드
### Heap 클래스
`compare` 함수를 전달해서 최대/최소, 원소 구조에 구애받지 않고 사용할 수 있다
```javascript
class Heap {
constructor(compare) {
this.heap = [];
this.compare = compare;
}
size() {
return this.heap.length;
}
// 새로운 원소를 힙에 추가
// 가장 끝에 넣고 제자리를 찾아서 올려준다.
push(value) {
this.heap.push(value);
this.siftUp(this.heap.length - 1);
}
// root를 뺀다.
// 가장 끝 값을 root로 올리고, 제자리를 찾아 내린다.
pop() {
if (this.size() <= 0) return null; // NOTE : 명시적으로 값을 반환해주는 쪽이 더 좋음
if (this.size() === 1) return this.heap.pop(); // NOTE : 이거 잊지 맙시다.
const ret = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown(0);
return ret;
}
// 인덱스 공식... (암기가 필요함...)
// parent: 자식 둘이 같은 부모를 공유한다. (1, 2) -> 3, => Math.floor((i - 1) / 2)
// child: left child 부터 생각하기. 부모 하나당 자식 2칸이 생긴다.
// - left: 0 -> 1, 1 -> 3, ... => (i * 2) + 1
// - right: left 옆. => (i * 2) + 2
// push와 함께 사용
// 제자리 찾아서 올라가는 단계
siftUp(idx) {
// heap 규칙에 어긋난다면 swap으로 올려준다.
// root이거나 heap 규칙에 잘 맞는다면 shiftUp 중단
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (this.compare(this.heap[idx], this.heap[parent])) {
this.swap(idx, parent);
idx = parent;
} else {
break;
}
}
}
// pop과 함께 사용
// 제자리 찾아서 내려가는 단계
siftDown(idx) {
while (true) {
const leftChild = idx * 2 + 1;
const rightChild = idx * 2 + 2;
let targetChild;
if (leftChild >= this.size()) break;
else if (rightChild >= this.size()) targetChild = leftChild;
else
targetChild = this.compare(this.heap[leftChild], this.heap[rightChild])
? leftChild
: rightChild;
if (this.compare(this.heap[targetChild], this.heap[idx])) {
this.swap(targetChild, idx);
idx = targetChild;
} else {
break;
}
}
}
// a 인덱스와 b인덱스의 값을 스왑
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
}
```
### 최대 힙
```javascript
const maxHeap = new Heap((a, b) => a > b);
```
### 최소 힙
```javascript
const minHeap = new Heap((a, b) => a < b);
```
### 단순 비교가 불가능한 원소를 담는 힙
```javascript
const minHeap = new Heap((a, b) => a.value < b.value);
const maxHeap = new Heap((a, b) => a.value > b.value);
const minHeap = new Heap(([c1, v1], [c2, v2]) => c1 < c2);
```