기술 블로그
js heapq 본문
반응형
class Heap {
constructor() {
this.heap = [null]; //0인덱스비워두기
}
size() {
return this.heap.length;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
heappush(value) {
this.heap.push(value);
let curIdx = this.heap.length - 1; // 현 노드 (위 value가 들어간 값)
let parIdx = (curIdx / 2) >> 0; // 부모노드
while (curIdx > 1 && this.heap[curIdx] < this.heap[parIdx]) {
//현 노드가 루트노드가 아니며, 동시에 부모가 더 값이 크면
this.swap(curIdx, parIdx); // 해당 값들 스왑
curIdx = parIdx; // 이제 위로 올라간게 현 노드
parIdx = (curIdx / 2) >> 0;
}
}
heappop() {
const min = this.heap[1]; //최솟값
if (this.heap.length <= 2) {
// 1개 이하 값만 남았다면
this.heap = [null]; //비우다/
} else {
//아니라면
this.heap[1] = this.heap.pop(); // 제일마지막 원소를 1번쨰 원소로
}
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[curIdx] > this.heap[leftIdx]) {
// 좌측 자식만 있다면
//자식이 더 작으면
this.swap(curIdx, leftIdx);
}
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;
}
}
const h = new Heap();
h.heappush(10);
console.log(h.heap);
h.heappush(11);
console.log(h.heap);
h.heappush(12);
console.log(h.heap);
h.heappush(13);
console.log(h.heap);
console.log(h.heappop());
console.log(h.heap);
h.heappop();
console.log(h.heap);
h.heappop();
console.log(h.heap);
h.heappop();
console.log(h.heap);
반응형
'알고리즘' 카테고리의 다른 글
[프로그래머스] 동영상 재생기 (0) | 2024.11.30 |
---|---|
[JS] 알고리즘을 위한 js - 2 문자열과 순회문 (0) | 2023.11.13 |
[JS] 알고리즘을 위한 js - 1 배열 (0) | 2023.11.13 |
[프로그래머스] 조이스틱 (0) | 2023.11.01 |
프로그래머스 체육복 (0) | 2023.10.26 |
Comments