[Algorithm] ์ต์ ํ(Heap)์ผ๋ก ์ฐ์ ์์ ํ ๊ตฌํํ๊ธฐ
ํ์ ํน์ง
์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ์ ๋ ๋๋ฆฌ ์ฌ์ฉํ๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์, ํ์ ํ์ ์๋ฃ๊ตฌ์กฐ๊ฐ ์ ์ฒด ์ฑ๋ฅ์ ๊ฒฐ์ ์ ์ธ ์ํฅ์ ๋ฏธ์น๋ค. ๋๋ฌธ์ ์ถ๊ฐ/์ญ์ ๋ฅผ ๋น ๋ฅด๊ฒ ์ํํ ์ ์๋ ์ฐ์ ์์ ํ๋ฅผ ์ฃผ๋ก ์ฌ์ฉํ๋ค.
์ฐ์ ์์ ํ๋ ์ผ๋ฐ ํ์ ๋น์ทํ์ง๋ง, ๊ฐ ์์๊ฐ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฉฐ, ์ฐ์ ์์๊ฐ ๋์ ์์๊ฐ ๋จผ์ ์ถ๋ ฅ๋๋ค๋ ์ ์ด ๋ค๋ฅด๋ค. ์ฐ์ ์์ ํ๋ ํฌ๊ฒ ๋ฐฐ์ด, ์ฐ๊ฒฐ๋ฆฌ์คํธ, ํ ์ด๋ ๊ฒ ์ธ ๊ฐ์ง ๋ฐฉ๋ฒ์ผ๋ก ๊ตฌํํ ์ ์๋ค. ๊ทธ์ค ์์ ์ด์ง ํธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๊ฐ๋ ํ์ผ๋ก ๊ตฌํํ๋ฉด ์ถ๊ฐ/์ ๊ฑฐ์ ํจ์จ์ฑ์ด ํฌ๊ฒ ํฅ์๋๋ค.
๊ตฌํ ๋ฐฉ๋ฒ | ์ฝ์ | ์ญ์ |
์์ ์๋ ๋ฐฐ์ด | O(1) | O(n) |
์์ ์๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ | O(1) | O(n) |
์ ๋ ฌ๋ ๋ฐฐ์ด | O(n) | O(1) |
์ ๋ ฌ๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ | O(n) | O(1) |
ํ | O(log n) | O(log n) |
์ด์ง ํธ๋ฆฌ๋ ๊ฐ ๋ถ๋ชจ ๋ ธ๋๊ฐ ์ผ์ชฝ/์ค๋ฅธ์ชฝ ์ต๋ 2๊ฐ์ ์์ ๋ ธ๋๋ฅผ ๊ฐ์ง ์ ์๋ ๊ตฌ์กฐ๋ฅผ ๊ฐ๋ฆฌํจ๋ค. ์์ ์ด์ง ํธ๋ฆฌ๋ ๋ง์ง๋ง ๋ ๋ฒจ์ ์ ์ธํ ๋ชจ๋ ๋ ๋ฒจ์ ์์ ํ ์ฑ์์ง ์ํ๋ก ์ ์งํด์ผ ํ๋ค. ๋๋ฌธ์ ์์ ๋ ธ๋๋ฅผ ์ถ๊ฐํ ๋ ์ผ์ชฝ๋ถํฐ ์ฐจ๋ก๋๋ก ์ฑ์์ผ ํ๋ค. ์๋ ์ด๋ฏธ์ง ์ผ์ชฝ์ ์๋ ํธ๋ฆฌ๋ 31๋ฒ ๋ ธ๋์ ์์์ ์ค๋ฅธ์ชฝ๋ถํฐ ์ฑ์ ๊ธฐ ๋๋ฌธ์ ์์ ์ด์ง ํธ๋ฆฌ๊ฐ ์๋๋ค.
ํ์ ํฌ๊ฒ ์ต๋ ํ(Max Heap), ์ต์ ํ(Min Heap)์ผ๋ก ๋ถ๋ฅ๋๋ค. ์ต๋ ํ์ ๋ถ๋ชจ ๋ ธ๋๊ฐ ํญ์ ์์ ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , ์ต์ ํ์ ๋ถ๋ชจ ๋ ธ๋๊ฐ ํญ์ ์์๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ฑฐ๋ฆฌ ๊ฐ์ด ๋ฎ์ ๋ ธ๋์ ๋์ ์ฐ์ ์์๋ฅผ ๋ถ์ฌํ๋ฏ๋ก, ๋ฃจํธ ๋ ธ๋๊ฐ ๊ฐ์ฅ ์งง์ ๊ฑฐ๋ฆฌ ๊ฐ(์ฐ์ ์์๊ฐ ๋์)์ ๊ฐ๋ ์ต์ ํ์ ์ฌ์ฉํ๋ ๊ฒ์ด ์ ์ ํ๋ค.
๋ฐฐ์ด๋ก ํํํ๋ ์ต์ ํ
์์์ ์ดํด๋ณธ ์์ ์ด์ง ํธ๋ฆฌ ํน์ฑ์ ์ด์ฉํ๋ฉด ๊ฐ ๋ ธ๋์ ์ธ๋ฑ์ค๋ฅผ ์๋ ๊ณต์์ผ๋ก ๊ณ์ฐํ ์ ์๋ค.
- ์ผ์ชฝ ์์ ๋ ธ๋ ์ธ๋ฑ์ค : ๋ถ๋ชจ ๋ ธ๋ ์ธ๋ฑ์ค × 2 + 1
- ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋ ์ธ๋ฑ์ค : ๋ถ๋ชจ ๋ ธ๋ ์ธ๋ฑ์ค × 2 + 2
- ๋ถ๋ชจ ๋ ธ๋ ์ธ๋ฑ์ค : (์์ ๋ ธ๋ ์ธ๋ฑ์ค - 1) / 2
์๋ฅผ๋ค์ด ๋ถ๋ชจ ๋ ธ๋์ ์ธ๋ฑ์ค๊ฐ 2๋ผ๋ฉด ์ผ์ชฝ ์์ ์ธ๋ฑ์ค๋ 5, ์ค๋ฅธ์ชฝ ์์ ์ธ๋ฑ์ค๋ 6์ด ๋๋ค. ์ด์ฒ๋ผ ํ ๋ ธ๋์ ์ธ๋ฑ์ค๋ง ์๋ฉด ํด๋น ๋ ธ๋์ ๋ถ๋ชจ/์์ ๋ ธ๋์ ์ธ๋ฑ์ค๋ ํ์ธํ ์ ์์ด์ ๋ฐฐ์ด ๊ตฌ์กฐ๋ก๋ ํธ๋ฆฌ๋ฅผ ํํํ ์ ์๋ค.
Enqueue
๋ ธ๋ ์ถ๊ฐ๋ ์ต์ ํ ์์ฑ(๋ถ๋ชจ ๋ ธ๋ ≤ ์์ ๋ ธ๋)์ ๋ง์กฑํ ๋๊น์ง ๋ถ๋ชจ ๋ ธ๋์ ๋น๊ตํ๋ฉฐ ์์น๋ฅผ ๊ตํํ๋ ๋ฐฉ์์ผ๋ก ์ด๋ค์ง๋ค. ๋ ธ๋ ์์น๋ฅผ ๊ตํํ๋ ๊ณผ์ ์ heapify-up์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. heapify-up์ ์ต์ ์ ๊ฒฝ์ฐ ํธ๋ฆฌ ๋์ด ๋งํผ ๋ฐ๋ณต๋๊ณ , ํธ๋ฆฌ ๋์ด๋ $\log_{2}V$์ด๋ฏ๋ก ๋ ธ๋ ์ถ๊ฐ์ ์๊ฐ ๋ณต์ก๋ ์ญ์ $\log_{2}V$๋ฅผ ๊ฐ๋๋ค.
- ์๋ก์ด ๋
ธ๋๋ฅผ ํ์ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ถ๊ฐํ๋ค —
heap.push(node)
- ์๋ก ์ถ๊ฐํ ๋ ธ๋๋ฅผ ๋ถ๋ชจ ๋ ธ๋์ ๋น๊ตํ์ฌ ๋ ์๋ค๋ฉด ์์น๋ฅผ ๋ฐ๊พผ๋ค — heapify-up
- ์๋ก ์ถ๊ฐํ ๋ ธ๋๊ฐ ๋ถ๋ชจ ๋ ธ๋๋ณด๋ค ํฌ๊ฑฐ๋, ๋ฃจํธ์ ๋๋ฌํ ๋๊น์ง ์ด ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค
๐ก ํธ๋ฆฌ์์ ๋์ด๋ ๋ฃจํธ ๋ ธ๋(๊น์ด 0)์์ ๋ฆฌํ ๋ ธ๋๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ์๋ฏธํ๋ค. ์์ ์ด์ง ํธ๋ฆฌ์์ ๊ฐ ๋ ๋ฒจ์ ๋ ธ๋ ์๋ ์ด์ ๋ ๋ฒจ ๋ ธ๋ ์์ 2๋ฐฐ๋ก ์ฆ๊ฐํ๋ค. ๋ฐ๋ผ์ ๋์ด๊ฐ $h$์ธ ์์ ์ด์ง ํธ๋ฆฌ๋ ์ต์ $2^{h}$์์ ์ต๋ $2^{h+1}-1$๊ฐ์ ๋ ธ๋๋ฅผ ๊ฐ์ง ์ ์๋ค. ์๋ฅผ ๋ค์ด, ๋์ด๊ฐ 2์ธ ํธ๋ฆฌ๋ ์ต๋ $2^{2+1}-1=7$๊ฐ์ ๋ ธ๋๋ฅผ ๊ฐ์ง ์ ์๋ค. ์ฆ, $V$๊ฐ์ ๋ ธ๋๋ฅผ ๊ฐ์ง ์์ ์ด์ง ํธ๋ฆฌ์ ๋์ด๋ $\log_{2}V$๋ก ๊ณ์ฐํ ์ ์๋ค.
Dequeue
๋ ธ๋ ์ ๊ฑฐ ์ญ์ ํ ์์ฑ์ ๋ง์กฑํ ๋๊น์ง ์์ ๋ ธ๋์ ๋น๊ตํ๋ฉฐ ์์น๋ฅผ ๊ตํํ๋ ๋ฐฉ์์ผ๋ก ์ด๋ค์ง๋ค. ๋ ธ๋ ์์น๋ฅผ ๊ตํํ๋ ๊ณผ์ ์ heapify-down์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. heapify-down์ heapify-up๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ์ต์ ์ ๊ฒฝ์ฐ ํธ๋ฆฌ ๋์ด ๋งํผ ๋ฐ๋ณต๋๊ณ , ํธ๋ฆฌ ๋์ด๋ $\log_{2}V$์ด๋ฏ๋ก ๋ ธ๋ ์ ๊ฑฐ์ ์๊ฐ ๋ณต์ก๋๋ $\log_{2}V$๋ฅผ ๊ฐ๋๋ค.
- ํ์ ๋ฃจํธ ๋
ธ๋๋ฅผ ์ ๊ฑฐํ๊ณ , ๋ง์ง๋ง ๋
ธ๋๋ฅผ ๋ฃจํธ๋ก ์ด๋ ์ํจ๋ค —
heap[0]=heap.pop()
- ๋ฃจํธ๋ก ์ด๋ํ ๋ ธ๋๋ณด๋ค ์์ ๋ ธ๋๊ฐ ๋ ์๋ค๋ฉด ์์น๋ฅผ ๋ฐ๊พผ๋ค — heapify-down
- ๋ฃจํธ๋ก ์ด๋ํ ๋ ธ๋๊ฐ ์์ ๋ ธ๋๋ณด๋ค ์๊ฑฐ๋, ๋ฆฌํ ๋ ธ๋์ ๋๋ฌํ ๋๊น์ง ์ด ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค
๐ก ๋ฐฐ์ด ๋ง์ง๋ง ์์๋ก ์ญ์ ํ ๋ฃจํธ ๋ ธ๋ ์๋ฆฌ๋ฅผ ์ฑ์ฐ๋ ์ด์ : ๋ฐฐ์ด ๋ง์ง๋ง ์์๋ฅผ ๊บผ๋ด๋ ์์ ์ $O(1)$ ์์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ๊ธฐ ๋๋ฌธ. ํ์์ ๋ฃจํธ ๋ ธ๋๋ฅผ ์ญ์ ํ๋ฉด ํ ๊ตฌ์กฐ๋ฅผ ์ ์งํ๊ธฐ ์ํด ๋ค๋ฅธ ๋ ธ๋๋ก ๊ทธ ์๋ฆฌ๋ฅผ ์ฑ์์ผ ํ๋ค. ๋ฐฐ์ด ๋ง์ง๋ง ์์๋ฅผ ์ฌ์ฉํ๋ฉด ์ถ๊ฐ์ ์ธ ์์ ์ด๋ ์์ด ๋น ๋ฅด๊ฒ ๋ฃจํธ์ ๋น ์๋ฆฌ๋ฅผ ์ฑ์ธ ์ ์์ด, ํ์ ์ฌ์ ๋ ฌ์ ์์ํ๋ ๊ฐ์ฅ ํจ์จ์ ์ธ ๋ฐฉ๋ฒ์ด๋ค.
์ฝ๋ ๊ตฌํ
class MinHeap {
constructor() {
this.heap = [];
}
// ์ผ์ชฝ ์์ ๋
ธ๋ ์ธ๋ฑ์ค = ๋ถ๋ชจ ๋
ธ๋ ์ธ๋ฑ์ค * 2 + 1
getLeftChildIndex(parentIdx) {
return 2 * parentIdx + 1;
}
// ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋ ์ธ๋ฑ์ค = ๋ถ๋ชจ ๋
ธ๋ ์ธ๋ฑ์ค * 2 + 2
getRightChildIndex(parentIdx) {
return 2 * parentIdx + 2;
}
// ๋ถ๋ชจ ๋
ธ๋ ์ธ๋ฑ์ค = (์์ ๋
ธ๋ ์ธ๋ฑ์ค - 1) / 2
getParentIndex(childIdx) {
return Math.floor((childIdx - 1) / 2);
}
// ์ฃผ์ด์ง ์ธ๋ฑ์ค์ ์์นํ (๋ถ๋ชจ)๋
ธ๋์ ์ผ์ชฝ ์์ ๋
ธ๋๊ฐ ์๋์ง ํ์ธ
// ์ผ์ชฝ ์์ ๋
ธ๋์ ์ธ๋ฑ์ค๊ฐ ์ ์ฒด ๋
ธ๋ ๊ฐฏ์๋ณด๋ค ์์ ๊ฒฝ์ฐ์๋ง ์์ ๋
ธ๋๊ฐ ์กด์ฌํ๋ค๊ณ ๊ฐ์ฃผ
hasLeftChild(idx) {
return this.getLeftChildIndex(idx) < this.heap.length;
}
// Checks if a right child exists for the given idx
hasRightChild(idx) {
return this.getRightChildIndex(idx) < this.heap.length;
}
// Checks if a parent exists for the given idx
hasParent(idx) {
return this.getParentIndex(idx) >= 0;
}
// Retrieves the left child's value for the given idx
leftChild(idx) {
return this.heap[this.getLeftChildIndex(idx)];
}
// Retrieves the right child's value for the given idx
rightChild(idx) {
return this.heap[this.getRightChildIndex(idx)];
}
// Retrieves the parent's value for the given idx
parent(idx) {
return this.heap[this.getParentIndex(idx)];
}
// Swaps the elements at the two given indexes
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
// Returns the minimum element without removing it
peek() {
return this.heap.length === 0 ? null : this.heap[0];
}
// Removes and returns the minimum element from the heap
remove() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const rootNode = this.heap[0];
this.heap[0] = this.heap.pop(); // ๊ฐ์ฅ ๋ง์ง๋ง์ ์๋ ๋
ธ๋๋ฅผ ๋ฃจํธ ๋
ธ๋๋ก ๋ง๋ค๊ณ
this.heapifyDown(); // ๋ค์ Min Heap ์์ฑ์ ๊ฐ๋๋ก ์กฐ์
return rootNode;
}
// Adds a new element to the heap
add(priority, value) {
this.heap.push({ priority, value: !value ? priority : value });
this.heapifyUp();
}
// Moves the last element up to its correct position in the heap
heapifyUp() {
let idx = this.heap.length - 1;
// ๋ถ๋ชจ ๋
ธ๋๊ฐ ์์ผ๋ฉด ์ต์
๋ ์ฒด์ด๋์ผ๋ก ์ธํด undefined ๋ฐํ -> while๋ฌธ ์กฐ๊ฑด ํต๊ณผ X
while (this.parent(idx)?.priority > this.heap[idx].priority) {
const parentIdx = this.getParentIndex(idx);
this.swap(parentIdx, idx);
idx = parentIdx;
}
}
// Moves the root element down to its correct position in the heap
heapifyDown() {
let idx = 0;
while (this.hasLeftChild(idx)) {
let smallestIdx = this.getLeftChildIndex(idx);
// ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋๊ฐ ์์ผ๋ฉด ์ต์
๋ ์ฒด์ด๋์ผ๋ก ์ธํด undefined ๋ฐํ -> while๋ฌธ ์กฐ๊ฑด ํต๊ณผ X
if (this.rightChild(idx)?.priority < this.leftChild(idx).priority) {
// ์ผ์ชฝ/์ค๋ฅธ์ชฝ ์์ ์ค ์ฐ์ ์์๊ฐ ๋ ๋์(priority ๊ฐ์ด ๋ ์์) ๋
ธ๋ ์ ํ
smallestIdx = this.getRightChildIndex(idx);
}
// ๋ถ๋ชจ ๋
ธ๋๊ฐ ์์ ๋
ธ๋๋ณด๋ค ๋ ์์ผ๋ฉด heapifyDown ์ค์ง
if (this.heap[idx].priority <= this.heap[smallestIdx].priority) break;
this.swap(idx, smallestIdx);
idx = smallestIdx;
}
}
// Prints all elements in the heap
printHeap(property = 'priority') {
console.log(this.heap.map((element) => element[property]).join(' '));
}
}
export default MinHeap;
๊ธฐ๋ณธ ๊ตฌ์กฐ
๋
ธ๋์ ์ธ๋ฑ์ค๋ฅผ ๊ณ์ฐํ๋ ๋ก์ง ๋ฑ์ ์์ฃผ ์ฌ์ฉํ๋ฏ๋ก ๋ฉ์๋๋ก ๋ฏธ๋ฆฌ ๊ตฌํํด๋๋ค. has*Child
๊ฐ์ ๋ฉ์๋๋ ์ฃผ์ด์ง ์ธ๋ฑ์ค์ ์์นํ ๋
ธ๋์ ์ผ์ชฝ/์ค๋ฅธ์ชฝ ์์ ๋
ธ๋๊ฐ ์๋์ง ํ์ธํ๋ค.
์ฃผ์ํ ์ ์ ๊ณ์ฐํ ์์ ๋
ธ๋์ ์ธ๋ฑ์ค๊ฐ ์ ์ฒด ๋
ธ๋ ๊ฐฏ์(heap.length
)๋ณด๋ค ์์ ๊ฒฝ์ฐ์๋ง ์กด์ฌํ๋ค๊ณ ๊ฐ์ฃผํด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด ํธ๋ฆฌ์ ๋ฃจํธ ๋
ธ๋ 1๊ฐ๋ฐ์ ์๋ค๋ฉด ๋ฐฐ์ด ๊ธธ์ด๋ 1์ด ๋๋ค. ์ด๋ ๋ฃจํธ ๋
ธ๋์ ๋ํ ์ผ์ชฝ/์ค๋ฅธ์ชฝ ์์ ๋
ธ๋์ ์ธ๋ฑ์ค๋ ๊ฐ๊ฐ 1, 2๋ก ๋ฐฐ์ด ๊ธธ์ด์ ๊ฐ๊ฑฐ๋ ํฌ๊ธฐ ๋๋ฌธ์ ์์ ๋
ธ๋๊ฐ ์๋ ๊ฑธ๋ก ์ฒ๋ฆฌํด์ผ ํ๋ค.
class MinHeap {
constructor() {
this.heap = []; // [{ priority: number, value: any }, ...]
}
// ์ ํธ๋ฆฌํฐ ํจ์
getLeftChildIndex(parentIdx) {
return 2 * parentIdx + 1;
}
getRightChildIndex(parentIdx) {
return 2 * parentIdx + 2;
}
getParentIndex(childIdx) {
return Math.floor((childIdx - 1) / 2);
}
hasLeftChild(idx) {
return this.getLeftChildIndex(idx) < this.heap.length;
}
hasRightChild(idx) {
return this.getRightChildIndex(idx) < this.heap.length;
}
hasParent(idx) {
return this.getParentIndex(idx) >= 0;
}
leftChild(idx) {
return this.heap[this.getLeftChildIndex(idx)];
}
rightChild(idx) {
return this.heap[this.getRightChildIndex(idx)];
}
parent(idx) {
return this.heap[this.getParentIndex(idx)];
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
// ...
}
์ถ๊ฐ (Enqueue)
์๋ก์ด ๋
ธ๋๋ฅผ ๋ฐ์ heap
๋ฐฐ์ด ๊ฐ์ฅ ๋์ ์ถ๊ฐํ๋ค. ๊ทธ ํ heapifyUp
๋ฉ์๋๋ฅผ ํธ์ถํด์ ํ ์์ฑ์ ๋ง์กฑํ ๋๊น์ง ๋ถ๋ชจ ๋
ธ๋์ ๋น๊ตํ๋ฉฐ ์์น๋ฅผ ๊ตํํ๋ค.
class MinHeap {
// ...
add(priority, value) {
this.heap.push({ priority, value: !value ? priority : value });
this.heapifyUp();
}
heapifyUp() {
let idx = this.heap.length - 1;
// ๋ถ๋ชจ ๋
ธ๋๊ฐ ์์ผ๋ฉด ์ต์
๋ ์ฒด์ด๋์ผ๋ก ์ธํด undefined ๋ฐํ -> while๋ฌธ ์กฐ๊ฑด ํต๊ณผ X
while (this.parent(idx)?.priority > this.heap[idx].priority) {
const parentIdx = this.getParentIndex(idx);
this.swap(parentIdx, idx);
idx = parentIdx;
}
}
}
์ญ์ (Dequeue)
remove
๋ฉ์๋๋ฅผ ํธ์ถํ๋ฉด ํธ๋ฆฌ์์ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ฃจํธ ๋
ธ๋๋ฅผ ์์ ์ ์ฅํ๊ณ , heap
๋ฐฐ์ด ๊ฐ์ฅ ๋ง์ง๋ง ๋
ธ๋๋ฅผ ๋ฃจํธ ๋
ธ๋๋ก ๋ณ๊ฒฝํ๋ค. ๊ทธ ํ ๋ค์ ํ ์์ฑ์ ์ ์งํ๊ธฐ ์ํด heapifyDown
๋ฉ์๋๋ฅผ ํธ์ถํ ํ ์์ ์ ์ฅํ๋ ๋ฃจํธ ๋
ธ๋๋ฅผ ๋ฐํํ๋ค. heapifyDown
์ ๋
ธ๋ ์ถ๊ฐ์ ๋ฐ๋๋ก ์์ ๋
ธ๋์ ๋น๊ตํ๋ฉฐ ์์น๋ฅผ ๊ตํํ๋ค. ์์ ๋
ธ๋๊ฐ 2๊ฐ ์๋ค๋ฉด ๋ ์ค ์ฐ์ ์์๊ฐ ๋์(priority
๊ฐ์ด ์์) ๋
ธ๋๋ฅผ ์ ํํด์ ๋น๊ตํ๋ค.
class MinHeap {
// ...
remove() {
if (this.heap.length === 0) return null; // ํ์ ๋
ธ๋๊ฐ ์์ ๋
if (this.heap.length === 1) return this.heap.pop(); // ํ์ ๋ฃจํธ ๋
ธ๋๋ง ์์ ๋
const rootNode = this.heap[0]; // ํ์ฌ ๋ฃจํธ ๋
ธ๋ ์์ ์ ์ฅ
this.heap[0] = this.heap.pop(); // ๊ฐ์ฅ ๋ง์ง๋ง์ ์๋ ๋
ธ๋๋ฅผ ๋ฃจํธ ๋
ธ๋๋ก ๋ง๋ค๊ณ
this.heapifyDown(); // ๋ค์ Min Heap ์์ฑ์ ๊ฐ๋๋ก ์กฐ์
return rootNode; // ์์ ์ ์ฅํ ๋ฃจํธ ๋
ธ๋ ๋ฐํ
}
heapifyDown() {
let idx = 0;
while (this.hasLeftChild(idx)) {
let smallestIdx = this.getLeftChildIndex(idx);
// ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋๊ฐ ์์ผ๋ฉด ์ต์
๋ ์ฒด์ด๋์ผ๋ก ์ธํด undefined ๋ฐํ -> while๋ฌธ ์กฐ๊ฑด ํต๊ณผ X
if (this.rightChild(idx)?.priority < this.leftChild(idx).priority) {
// ์ผ์ชฝ/์ค๋ฅธ์ชฝ ์์ ์ค ์ฐ์ ์์๊ฐ ๋ ๋์(priority ๊ฐ์ด ๋ ์์) ๋
ธ๋ ์ ํ
smallestIdx = this.getRightChildIndex(idx);
}
// ๋ถ๋ชจ ๋
ธ๋๊ฐ ์์ ๋
ธ๋๋ณด๋ค ๋ ์์ผ๋ฉด heapifyDown ์ค์ง
if (this.heap[idx].priority <= this.heap[smallestIdx].priority) break;
this.swap(idx, smallestIdx);
idx = smallestIdx;
}
}
}
๋๋ฒ๊น ๋ฉ์๋
์ต์ ํ์ ์ฌ์ฉํ ๋ ์์ฃผ ์ฌ์ฉํ๋ ๋๋ฒ๊น
์ฉ ๋ฉ์๋๋ฅผ ์ถ๊ฐํ๋ค. ์ฝ๊ธฐ์ ์ฉ ๋ฉ์๋ peek
์ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋
ธ๋ ์ ๋ณด๋ฅผ ๋ฐํํ๋ค. ์ต์ ํ์์ ํญ์ ๋ฃจํธ๋
ธ๋์ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ผ๋ฏ๋ก $O(1)$ ์์ ์๊ฐ์ผ๋ก ์ํํ ์ ์๋ค.
class MinHeap {
// ...
peek() {
return this.heap.length === 0 ? null : this.heap[0];
}
printHeap(property = 'priority') {
console.log(this.heap.map((element) => element[property]).join(' '));
}
}
export default MinHeap;
peek
: ํ ์ํ ๋ณ๊ฒฝ ์์ด ํ์ฌ ๋ฃจํธ ๋ ธ๋(๋ค์์ ๋ฐํ๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ ธ๋)์ ์ ๋ณด๋ง ๋ฐํprintHeap
: ํ์ฌ ํ์ ์ ์ฅ๋ ๋ชจ๋ ๋ ธ๋๋ฅผ ์ฝ์๋ก ์ถ๋ ฅ
์ฐ์ ์์ ํ
MinHeap
ํด๋์ค๋ฅผ ํ์ฅํด์ ์ฐ์ ์์ ํ ๊ธฐ๋ฅ์ ํนํ๋ ์ฌ๋ฌ ๋ฉ์๋๋ฅผ ์ถ๊ฐํ๋ค. ์ฐธ๊ณ ๋ก ์๋ธ ํด๋์ค์ ์์ฑ์(constructor
)๋ฅผ ์๋ตํ๋ฉด ๋ด๋ถ์ ์ผ๋ก ๋ถ๋ชจ ํด๋์ค์ ์์ฑ์ ํจ์๋ฅผ ํธ์ถํ๋ค(super()
). ๋ถ๋ชจ/์๋ธ ํด๋์ค ์์ฑ์๊ฐ ๋ฐ๋ ํ๋ผ๋ฏธํฐ๊ฐ ๋์ผํ๊ฑฐ๋ ์๋ค๋ฉด ์๋ตํด๋ ๋ฌด๋ฐฉํ๋ค.
class PriorityQueue extends MinHeap {
get size() {
return this.heap.length;
}
get isEmpty() {
return this.size === 0;
}
enqueue(priority, value) {
this.add(priority, value);
}
dequeue() {
return this.remove();
}
clear() {
this.heap = [];
}
contains(value) {
return this.heap.some((element) => element.value === value);
}
// ...
}
๋ ํผ๋ฐ์ค
JavaScript๋ก Heap | Priority Queue ๊ตฌํํ๊ธฐ | jun-choi-4928
Min Heap in JavaScript | GeeksforGeeks
๊ธ ์์ ์ฌํญ์ ๋ ธ์ ํ์ด์ง์ ๊ฐ์ฅ ๋น ๋ฅด๊ฒ ๋ฐ์๋ฉ๋๋ค. ๋งํฌ๋ฅผ ์ฐธ๊ณ ํด ์ฃผ์ธ์
'๐ช Programming' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote
๋ค๋ฅธ ๊ธ
-
[React] ํฌ๋กฌ ํ์ฅ ํ๋ก๊ทธ๋จ ๊ฐ๋ฐ ๋ฐฐ๊ฒฝ ์ง์ ๋ฐ ํํ ๋ฆฌ์ผ
[React] ํฌ๋กฌ ํ์ฅ ํ๋ก๊ทธ๋จ ๊ฐ๋ฐ ๋ฐฐ๊ฒฝ ์ง์ ๋ฐ ํํ ๋ฆฌ์ผ
2024.05.28 -
[Algorithm] ์๋ฐ์คํฌ๋ฆฝํธ Map์ผ๋ก ๊ตฌํํ๋ LRU Cache ์๊ณ ๋ฆฌ์ฆ
[Algorithm] ์๋ฐ์คํฌ๋ฆฝํธ Map์ผ๋ก ๊ตฌํํ๋ LRU Cache ์๊ณ ๋ฆฌ์ฆ
2024.05.28 -
[Algorithm] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ — ์ต๋จ ๊ฒฝ๋ก ์ฐพ๊ธฐ
[Algorithm] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ — ์ต๋จ ๊ฒฝ๋ก ์ฐพ๊ธฐ
2024.05.28 -
[CS] ์ปดํจํฐ์ ์ค์(Real Number) ํํ - ๊ณ ์ ์์์ , ๋ถ๋ ์์์ , ์ง์ ํ๊ธฐ๋ฒ, ์ ๊ทํ ์ด ์ ๋ฆฌ
[CS] ์ปดํจํฐ์ ์ค์(Real Number) ํํ - ๊ณ ์ ์์์ , ๋ถ๋ ์์์ , ์ง์ ํ๊ธฐ๋ฒ, ์ ๊ทํ ์ด ์ ๋ฆฌ
2024.05.27