=> 힙은 우선순위 큐의 개념을 활용한 자료구조이다. 요소가 삽입, 삭제될 때마다 바로 정렬되는 특징이 있다. 최대힙, 최소힙이 있으며 JS에서는 직접 구현해서 써야한다. 또한 힙은 이진트리이기에 배열로 만들 수 있다.
class MaxHeap {
constructor() {
this.heap = [null];
}
push(value) {
this.heap.push(value);
let currentIndex = this.heap.length - 1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] < value) {
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop();
console.log('heap: ', this.heap);
console.log('heap[1]: ', this.heap[1]);
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while (
this.heap[currentIndex] < this.heap[leftIndex] ||
this.heap[currentIndex] < this.heap[rightIndex]
) {
if (this.heap[leftIndex] < this.heap[rightIndex]) {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[rightIndex];
this.heap[rightIndex] = temp;
currentIndex = rightIndex;
} else {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[leftIndex];
this.heap[leftIndex] = temp;
currentIndex = leftIndex;
}
leftIndex = currentIndex * 2;
rightIndex = currentIndex * 2 + 1;
}
return returnValue;
}
}
const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap);
const array = [];
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
console.log(array);
=> 계속 최대값이나 최소값을 구해야 하는 상황이면 logn으로 삽입, 삭제가 가능한 힙을 사용하자
class MinHeap {
constructor() {
this.heap = [null];
}
push(value) {
this.heap.push(value);
let currentIndex = this.heap.length - 1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] > value) {
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop();
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while (this.heap[currentIndex] > this.heap[leftIndex] ||
this.heap[currentIndex] > this.heap[rightIndex]) {
if (this.heap[leftIndex] > this.heap[rightIndex]) {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = value;
this.heap[rightIndex] = temp;
currentIndex = rightIndex;
} else {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = value;
this.heap[leftIndex] = temp;
currentIndex = leftIndex;
}
leftIndex = currentIndex * 2;
rightIndex = currentIndex * 2 + 1;
}
return returnValue;
}
}
=> 최소 힙은 반대로 구현하면 된다.