아래와 같은 queue가 있을 때,
shift()를 하면 5 ➔ 3 ➔ 9 ㆍㆍㆍ ➔ 6 순으로 요소들이 나올 것 이다. 이 때 들어온 순서에 상관없이, 일정한 기준에 따라 요소들이 나오도록 할 수 있는데, 이것을 priority queue라고 한다.
queue에서 가장 작은 값을 제거하고 싶을 때
1. Math.min()
O(n)의 시간 복잡도를 가진다.
let queue = [5, 3, 9, 4, 1, 2, 6];
let min = Math.min(...queue); // 큐에서 가장 작은 값을 찾음
let index = queue.indexOf(min); // 가장 작은 값의 인덱스를 찾음
queue.splice(index, 1); // 가장 작은 값 제거2. sort()
O(n log n)의 시간 복잡도를 가진다.
let queue = [5, 3, 9, 4, 1, 2, 6];
queue.sort((a,b) => a-b); // 오름차순으로 정렬
queue.shift(); // 가장 작은 값 제거두 가지 방법중에서는 2번의 방법이 시간 복잡도 측면에서 이득을 볼 수 있지만, 새로운 원소들이 추가하는 경우에 매번 정렬을 해줘야 한다는 단점이 있다.
💡 원소를 추가할 때마다, 오름차순으로 알아서 정렬해주는 자료구조있다면 편할 것이다. heap이라는 자료구조를 통해 priority queue를 구현할 수 있다.
힙(Heap)
heap은 min heap과 max heap으로 나누어져 있다. 각각의 정의는 아래와 같다.
- min heap: 자식 노드의 값이 부모 노드의 값보다 큰 트리 형태의 자료구조
- max heap: 자식 노드의 값이 부모 노드의 값보다 작은 트리 형태의 자료구조
힙(Heap) 구현
다른 언어에서는 내장 라이브러리나 함수같은게 있지만 자바스크립트에서는 외부 라이브러리를 사용하거나 직접 구현을 해야 한다. 코딩테스트 환경에서는 외부 라이브러리를 사용할 수 없으니 직접 구현해서 사용 해야한다!
힙은 부모와 자식 간에 다음과 같은 관계가 성립한다.
- 왼쪽 자식의 index =
부모의 index * 2 + 1 - 오른쪽 자식의 index =
부모의 index * 2 + 2 - 부모의 index =
Math.floor((자식의 index - 1) / 2)
기본적으로 사용 될 메소드는 아래 코드와 같다!
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]];
}
}삽입 연산 - O(log n)
min heap의 삽입 연산은 다음과 같은 단계로 이루어진다.
1. Heap의 마지막 위치에 요소를 추가
2. 새로운 요소를 추가한 위치부터, 부모 노드와 새로 추가된 노드의 값을 비교
3. 만약 새로 추가된 노드의 값이 부모 노드의 값보다 작다면, 부모 노드와 새로 추가된 노드의 위치를 바꾼다.
4. 이전 단계에서 교환된 새로 추가된 노드와 부모 노드의 값 비교를 반복한다.
✏️ bubbleUp
Heap에 값을 삽입할 때 부모와 비교해서 값이 크거나 작으면 부모와 값을 교환해서 올바르게 정렬이 될 때 까지 올라가는 것을 말한다.
1. 새로 추가된 2가 부모 노드 6과 비교했을 때 2가 작으므로 교체한다.
2. 부모 노드 3과 비교했을 때 2가 작으므로 교체한다.
3. 부모 노드 1과 비교했을 때 2가 크므로 더 이상 교체하지 않는다.
// 새로운 노드를 추가하는 메서드
add(value) {
this.heap.push(value); // 힙의 끝에 새로운 노드 추가
this.bubbleUp(); // 새로운 값이 추가된 위치에서 bubbleUp() 수행
}
bubbleUp() {
let index = this.heap.length - 1; // 새로운 노드가 추가된 위치
let parentIdx = Math.floor((index - 1) / 2); // 부모 노드의 위치
// 부모 노드가 존재하고 새로운 노드가 부모 노드보다 작은 경우
while (this.heap[parentIdx] && this.heap[index][1] < this.heap[parentIdx][1] ) {
this.swap(index, parentIdx); // 두 노드의 값을 교체
index = parentIdx; // 인덱스를 부모 노드의 인덱스로 변경
parentIdx = Math.floor((index - 1) / 2); // 새로운 부모 노드의 인덱스 계산
}
}삭제 연산 - O(log n)
min heap의 삭제 연산은 다음과 같은 단계로 이루어진다.
1. Heap에서 가장 작은 값을 가진 노드(루트 노드)를 제거한다.
2. Heap의 맨 마지막에 있는 노드를 새로운 루트 노드로 이동시킨다.
3. 새로운 루트 노드와 자식 노드의 값을 비교하여, 자식 노드의 값이 작다면 루트 노드의 위치를 교환한다.
4. 이전 단계에서 교환된 새로 추가된 루트 노드와 자식 노드의 값 비교를 반복한다.
✏️ bubbleDown
루트 노드를 삭제하고 마지막 노드를 루트로 올리고 루트 노드와 아래 자식 노드들과 비교해서 값이 크거나 작으면 자식과 값을 교환해서 올바르게 정렬이 될 때 까지는 내려가는 것을 말한다.
1. 루트 노드가 삭제 되고, 빈 루트 노드 자리에는 힙의 마지막 노드 7을 가져온다.
2. 새로운 루트 노드7과 자식 노드를 비교했을 때 7이 더 크므로 교체해야 한다. 이때 자식 노드 중 더 작은 값인 3과 7이 교체된다.
3. 7이 아직 자식 노드들보다 더 크기 때문에 교체되어야 한다. 자식 노드 중 더 작은 값이 5와 7이 교체된다.
4. 7이 자식 노드들보다 작으므로 더 이상 교체하지 않는다.
poll() {
if (this.heap.length === 1) {
return this.heap.pop(); // 힙의 크기가 1인 경우, 힙에서 값을 삭제하고 return
}
const value = this.heap[0]; // 힙의 최소값(루트 노드의 값)을 저장
this.heap[0] = this.heap.pop(); // 힙의 끝에 있는 값을 루트 노드로 이동
this.bubbleDown(); // 루트 노드에서 bubbleDown을 수행
return value; // 삭제한 최소값 return
}
bubbleDown() {
let index = 0; // 루트 노드의 index
let leftIdx = index * 2 + 1; // 왼쪽 자식 노드의 index
let rightIdx = index * 2 + 2; // 오른쪽 자식 노드의 index
// 왼쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작거나 오른쪽 자식 노드가 존재 하면서 값이 루트 노드보다 작은 경우
while ((this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
(this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])) {
let smallerIdx = leftIdx; // 왼쪽 자식 노드가 더 작다고 가정
// 오른쪽 자식 노드가 더 작다면
if (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[smallerIdx][1] ) {
smallerIdx = rightIdx; // 오른쪽 자식 노드의 index로 변경
}
this.swap(index, smallerIdx); // 두 노드의 값을 교체
index = smallerIdx; // index를 더 작은 값의 자식 노드의 index로 변경
leftIdx = index * 2 + 1; // 왼쪽 자식 노드의 index 계산
rightIdx = index * 2 + 2; // 오른쪽 자식 노드의 index 계산
}
}전체 코드(주석 제거)
💡 자바스크립트로 코딩테스트 문제를 풀 때 힙을 직접 구현해서 풀어야"만" 해결할 수 있는 문제가 많지는 않다. 그래도 모르는 것보다는 알아두는 것이 훨씬 좋다!
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]];
}
add(value) {
this.heap.push(value);
this.bubbleUp();
}
poll() {
if (this.heap.length === 1) {
return this.heap.pop();
}
const value = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return value;
}
bubbleUp() {
let index = this.heap.length - 1;
let parentIdx = Math.floor((index - 1) / 2);
while (this.heap[parentIdx] && this.heap[index][1] < this.heap[parentIdx][1]) {
this.swap(index, parentIdx);
index = parentIdx;
parentIdx = Math.floor((index - 1) / 2);
}
}
bubbleDown() {
let index = 0;
let leftIdx = index * 2 + 1;
let rightIdx = index * 2 + 2;
while ((this.heap[leftIdx] && this.heap[leftIdx][1] < this.heap[index][1]) ||
(this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[index][1])) {
let smallerIdx = leftIdx;
if (this.heap[rightIdx] && this.heap[rightIdx][1] < this.heap[smallerIdx][1]) {
smallerIdx = rightIdx;
this.swap(index, smallerIdx);
index = smallerIdx;
leftIdx = index * 2 + 1;
rightIdx = index * 2 + 2;
}
}
}