힙의 시간복잡도
// 최대 힙
class Heap {
constructor() {
this.heap = []; // n:parent, 2*n+1:left child, 2*n+2:right child
}
}
insert(value) {
this.heap.push(val);
let cur = this.heap.length-1;
let parent = Math.floor(cur-1)/2);
// 추가한 값보다 부모 노드의 값이 더 큰 값이 나올 때 까지 root를 향해 Swap해간다.
while(parent < val) {
this.swap(this.heap[parent], this.heap[cur]);
cur = parent;
parent = Math.floor(cur-1)/2);
}
}
pop() {
// root 값과 마지막 값을 swap한다.
const lastIndex = this.heap.length-1;
this.swap(this.heap[0], this.heap[lastIndex]);
let value = this.heap.pop();
let cur = 0;
while(cur < lastIndex) {
let leftChild = cur*2+1;
let rightChild = cur*2+2;
// left child가 없다면 해당 노드는 자식 노드가 없다.
if(leftChild >= lastIndex) {
break;
}
// left child만 가지고 있을 경우
else if(rightChild >= lastIndex) {
// 자식 노드의 값이 더 크다면 swawp한다.
if(this.heap[cur] < this.heap[leftChild]) {
this.swap(this.heap[cur], this.heap[rightChild]);
cur = leftChild;
}
else {
break;
}
}
// left, right child 모두 가지고 있을 경우
else {
// 자식 모두가 자신보다 값이 클 경우 더 큰 값과 swap한다.
if(this.heap[cur] < this.heap[leftChild] && this.heap[cur] < this.heap[rightChild]) {
if(this.heap[leftChild] > this.heap[rightChild]) {
this.swap(this.heap[cur], this.heap[leftChild]);
cur = leftChild;
} else {
this.swap(this.heap[cur], this.heap[rightChild]);
cur = rightChild;
}
}
// 어느 한 쪽 자식의 값만 자신의 값보다 더 크다면 그 값과 swap한다.
else if(this.heap[cur] < this.heap[leftChild]) {
this.swap(this.heap[cur], this.heap[leftChild]);
cur = leftChild;
} else if(this.heap[cur] < this.heap[rightChild]) {
this.swap(this.heap[cur], this.heap[rightChild]);
cur = rightChild;
} else {
break;
}
}
}
return value
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
size() {
return this.heap.length;
}
중괄호나 괄호가 빠져있는 코드가 중간중간 있네요.
그리고 swap메소드가 실제로 동작하는건가요? 제가 다음 코드로 swap을 해봤는데 잘 안되네요.. 제 코드에 어떤 문제라도 있을까요?