이 강좌에서는 자바스크립트로 절댓값 힙(Absolute Value Heap)을 구현하는 방법에 대해 배워보겠습니다. 절댓값 힙은 두 가지 기준으로 정렬된 힙 구조로, 주로 절댓값을 기준으로 데이터를 정렬합니다. 예를 들어, 절댓값이 같은 경우에는 실제 값에 따라 정렬됩니다.
문제 설명
절댓값 힙을 구성하는 방법과 이를 통해 주어진 작업을 수행하는 알고리즘 문제를 해결해 보겠습니다. 문제는 다음과 같습니다.
정수로 이루어진 배열이 주어질 때, 절댓값 힙을 이용하여 가장 작은 절댓값을 가진 수를 삭제하고 그 값을 반환하는 작업을 진행하세요. 절댓값이 동일한 경우에는 더 작은 값을 우선하여 삭제합니다.
입력 형식
["I 5", "I -5", "I 3", "I -2", "I 0", "I 4", "D 1", "D 1"]
출력 형식
[0, -2, 3, 4]
문제 풀이 과정
절댓값 힙을 구현하기 위해, 자바스크립트의 배열을 사용할 수 있습니다. 배열을 선언하고, 이를 기반으로 삽입 및 삭제 작업을 수행하는 메서드를 구현합니다.
1단계: 힙 클래스 정의
우선 힙의 기본 구조를 설계합니다. 힙은 항상 특정한 규칙에 따라 부모 노드와 자식 노드가 관계를 맺어야 합니다. 절댓값이 작은 순서로 정렬되며, 절댓값이 같을 경우 원래 값이 작은 순서로 정렬됩니다.
class AbsoluteValueHeap {
constructor() {
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
bubbleUp(index) {
const element = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (this.isCorrectOrder(element, parent)) break;
this.heap[index] = parent;
index = parentIndex;
}
this.heap[index] = element;
}
isCorrectOrder(child, parent) {
if (Math.abs(child) < Math.abs(parent)) return true;
if (Math.abs(child) > Math.abs(parent)) return false;
return child < parent;
}
delete() {
if (this.heap.length === 0) return null;
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.bubbleDown(0);
}
return min;
}
bubbleDown(index) {
const element = this.heap[index];
const length = this.heap.length;
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (!this.isCorrectOrder(element, leftChild)) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && !this.isCorrectOrder(element, rightChild)) ||
(swap !== null && !this.isCorrectOrder(leftChild, rightChild))
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
index = swap;
}
this.heap[index] = element;
}
peek() {
return this.heap[0] || null;
}
}
2단계: 작업 처리 함수 만들기
이제 절댓값 힙을 기반으로 다양한 명령어를 처리하는 함수를 만들겠습니다. 명령어는 ‘I’는 삽입, ‘D’는 삭제를 나타냅니다.
function processCommands(commands) {
const heap = new AbsoluteValueHeap();
const results = [];
for (const command of commands) {
const [action, value] = command.split(' ');
const num = parseInt(value);
if (action === 'I') {
heap.insert(num);
} else if (action === 'D' && num === 1) {
const deleted = heap.delete();
results.push(deleted !== null ? deleted : 0);
} else if (action === 'D' && num === -1) {
// Min heap으로 구현하기 때문에 삭제할 필요 없음
const deleted = heap.delete();
results.push(deleted !== null ? deleted : 0);
}
}
return results;
}
3단계: 전체 코드 요약
이제까지 만들어진 코드를 모두 결합해 전체 코드를 정리해보겠습니다.
class AbsoluteValueHeap {
// 이전에 정의한 코드를 활용합니다.
}
function processCommands(commands) {
// 이전에 정의한 코드를 활용합니다.
}
// 테스트 예제 실행
const commands = ["I 5", "I -5", "I 3", "I -2", "I 0", "I 4", "D 1", "D 1"];
console.log(processCommands(commands)); // [0, -2, 3, 4]
결론
이번 강좌에서는 자바스크립트로 절댓값 힙을 구현하여 주어진 문제를 해결하는 과정을 살펴보았습니다. 알고리즘의 이해를 돕기 위해 기본적인 힙 정렬 개념과 절댓값을 기준으로 하는 힙의 동작 원리를 설명하였습니다. 이 강좌를 바탕으로 더 발전된 자료구조와 알고리즘 문제 해결 능력을 키워나가길 바랍니다.