์์ํ๊ธฐ ์ ์ ์ด์ง ํธ๋ฆฌ (์ด์ง ํธ๋ฆฌ์์ ๊ฐ ๋
ธ๋๋ ์ผ์ชฝ ํ์ ํธ๋ฆฌ ์ ๋ชจ๋ ํค๋ณด๋ค ํฌ๊ณ ์ค๋ฅธ์ชฝ ํ์ ํธ๋ฆฌ ์ ๋ชจ๋ ํค๋ณด๋ค ์์ ํค ๋ฅผ ์ ์ฅํจ ) ์ ๋ํด ์๊ณ ์๋ค๊ณ ๊ฐ์ ํฉ๋๋ค . ๋ฐ๋ฉด ์ด์ง ํ์ ์ต์ ํ ๋๋ ์ต๋ ํ ์์ ์์ฑ์ ๋ง์กฑํ๋ ์์ ํ ์ด์ง ํธ๋ฆฌ์
๋๋ค.. ์ด๋ฌํ ๊ฐ๋
์ ์ต์ํ์ง ์์ ๊ฒฝ์ฐ ์ด๋ฌํ ๊ฐ๋
์ ์ ์ ์กฐ๊ฑด์ผ๋ก ์ดํดํ๋ ๊ฒ์ด ์ข์ต๋๋ค. ๋ง์ ์ด๋ณด ํ๋ก๊ทธ๋๋จธ๋ ํ, ์ต์ ํ ๋ฐ ์ฐ์ ์์ ํ์ ๊ฐ๋
์ผ๋ก ์ด๋ ค์์ ๊ฒช์ ์ ์์ต๋๋ค. ์ด ๊ฒ์๋ฌผ์์๋ ํ์ด Min-Heap๊ณผ ์ด๋ป๊ฒ ๋ค๋ฅธ์ง, ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ์ฌ Min Heap์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์์ธํ ์์๋ณด๊ฒ ์ต๋๋ค.
๊ทธ๋ฆผ 1: ๊ฐ๋จํ ์ต์ ํ
๋
ธ๋์ ๊ฐ๊ณผ ์ต์ ํ ๋๋ ์ต๋ ํ์ ํ์ ๊ฐ ์ฌ์ด์ ํ์ํ ๊ด๊ณ๊ฐ ์์์ ์ ์ํ์ญ์์ค. ์๋ฅผ ๋ค์ด ๋ฃจํธ์ ์ผ์ชฝ ํ์ ํธ๋ฆฌ์ ์๋ ๋ชจ๋ ๋
ธ๋์ ๊ฐ์ด ์ค๋ฅธ์ชฝ ํ์ ํธ๋ฆฌ์ ๋ชจ๋ ๋
ธ๋์ ๋ํ ๊ฐ๋ณด๋ค ํด ์ ์์ต๋๋ค.
๊ทธ๋ฆผ 2: ์ผ์ชฝ ์์ ๋
ธ๋ > ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋๊ฐ ์๋ ์ต์ ํ
๊ทธ๋ฆผ 3: ๊ทธ๋ฆผ 2์ ํ ๋ฐฐ์ด ํํ
๋ค์ ์์์ ์ฌ์ฉํ์ฌ ๋ถ๋ชจ, ์ค๋ฅธ์ชฝ ๋๋ ์ผ์ชฝ ์์ ๋
ธ๋์ ๊ฐ๋จํ ์ก์ธ์คํ๋ ๋ฐฉ๋ฒ์ ์์ฐํ ๊ฒ์
๋๋ค.
์ต์ ํ์ด๋ ๋ฌด์์ ๋๊น?
์ต์ ํ์ 'n' ์์ค์ ๋ชจ๋ ๋ ธ๋๊ฐ 'n+1' ์์ค์ ์์ ๋ ธ๋๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๊ฐ์ ์ ์ฅํ๋ ์์ฑ์ ๊ฐ์ง๊ณ ์์ต๋๋ค. ๋ฃจํธ๋ ์์๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๊ฐ์ ๊ฐ๊ณ , ์ฐจ๋ก๋ก ์์๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๊ฐ์ ๊ฐ๊ธฐ ๋๋ฌธ์ ๋ฃจํธ๋ ํธ๋ฆฌ์ ๋ชจ๋ ๊ฐ ์ค ์ต์๊ฐ์ ์ ์ฅํฉ๋๋ค.์


Java์ ์ต์ ํ ํํ
์ต์ ํ์ ๋ํ๋ด๋ ๋ฐ ๊ฐ์ฅ ์ผ๋ฐ์ ์ผ๋ก ์ฌ์ฉ๋๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ ๊ฐ๋จํ ๋ฐฐ์ด์ ๋๋ค. ์ด๋ณด์๋ก์ "๋ฐฐ์ด"๊ณผ "์ต์ ํ"์ ํผ๋ํ ํ์๊ฐ ์์ต๋๋ค. ์ต์ ํ์ ๋ ธ๋/์์ ๊ฐ์ด ๋ฐฐ์ด์ ์ ์ฅ๋๋ ๊ฒ์ผ๋ก ๋ณผ ์ ์์ต๋๋ค . Java์ " ํธ๋ฆฌ " ๋ฅผ ์ ์ฅํ ๋ฐ์ดํฐ ๊ตฌ์กฐ๊ฐ ์๊ณ ์ด๋ฅผ ์ํด "๋ ธ๋"๋ฅผ ๊ตฌ์ถํ๊ฑฐ๋ " ๊ทธ๋ํ "๋ฅผ ์ ์ฅํ๊ธฐ ์ํด "๋งต"์ ์ฌ์ฉํ๋ ๋ฐฉ์๊ณผ ๊ฐ์ต๋๋ค .
- minHeap []์ ์ธ๋ฑ์ค " i = 0 ์ ๋ฃจํธ๊ฐ ์๋ ์ ์ ๋ฐฐ์ด์ ๋๋ค . ".
- minHeap[(i - 1) / 2]๋ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๋ฐํํฉ๋๋ค.
- minHeap[(i * 2) + 2]๋ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๋ฅผ ๋ฐํํฉ๋๋ค.
- minHeap[(i * 2) + 1]์ ์ผ์ชฝ ์์ ๋ ธ๋๋ฅผ ๋ฐํํฉ๋๋ค.
Java์์ ์ต์ ํ ๊ตฌํ - ๋ฐฐ์ด ์ฌ์ฉ
์ถ๊ฐํ ์์์ ํ์ฌ ์์น๋ฅผ ์ธ๋ฑ์ค๋ก, ๋ฐฐ์ด์ ์ ์ฒด ํฌ๊ธฐ๋ฅผ ํฌ๊ธฐ๋ก ํ๋ ๋ฐฐ์ด์ ์ฌ์ฉํ๋ ํ์ ๊ธฐ๋ณธ ๊ตฌํ์ ์ดํด๋ณด๊ฒ ์ต๋๋ค.
import java.util.Arrays;
public class MinHeap
{
private int[] Heap;
private int index;
private int size;
public MinHeap(int size) {
this.size = size;
this.index = 0;
Heap = new int[size];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return (i * 2) + 1;
}
private int rightChild(int i) {
return (i * 2) + 2;
}
private boolean isLeaf(int i) {
if (rightChild(i) >= size || leftChild(i) >= size) {
return true;
}
return false;
}
public void insert(int element) {
if (index >= size) {
return;
}
Heap[index] = element;
int current = index;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
index++;
}
// removes and returns the minimum element from the heap
public int remove() {
// since its a min heap, so root = minimum
int popped = Heap[0];
Heap[0] = Heap[--index];
minHeapify(0);
return popped;
}
// heapify the node at i
private void minHeapify(int i) {
// If the node is a non-leaf node and any of its child is smaller
if (!isLeaf(i)) {
if (Heap[i] > Heap[leftChild(i)] ||
Heap[i] > Heap[rightChild(i)]) {
if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
swap(i, leftChild(i));
minHeapify(leftChild(i));
} else {
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap() {
for (int i = (index - 1 / 2); i >= 1; i--) {
minHeapify(i);
}
}
// Function to print the contents of the heap
public void printHeap() {
for (int i = 0; i < (index / 2); i++) {
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < index)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < index)
System.out.print(" Right :" + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
private void swap(int x, int y) {
int tmp;
tmp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = tmp;
}
public static void main(String[] arg)
{
MinHeap minHeap = new MinHeap(7);
minHeap.insert(3);
minHeap.insert(13);
minHeap.insert(7);
minHeap.insert(16);
minHeap.insert(21);
minHeap.insert(12);
minHeap.insert(9);
minHeap.minHeap();
System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
minHeap.printHeap();
System.out.println("\nThe Min Value is : " + minHeap.remove());
System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
minHeap.printHeap();
}
}
์ฐ์ถ
์ต์ ํ: [3, 13, 7, 16, 21, 12, 9] ๋ถ๋ชจ: 3 ์ผ์ชฝ: 13 ์ค๋ฅธ์ชฝ:7 ๋ถ๋ชจ: 13 ์ผ์ชฝ: 16 ์ค๋ฅธ์ชฝ:21 ๋ถ๋ชจ: 7 ์ผ์ชฝ: 12 ์ค๋ฅธ์ชฝ:9 ์ต์๊ฐ is : 3 Min Heap is : [7, 13, 9, 16, 21, 12, 9] // ๋ฃจํธ๋ฅผ ์ ๊ฑฐํ ํ Parent : 7 Left : 13 Right :9 Parent : 13 Left : 16 Right :21 Parent : 9 ์ผ์ชฝ : 12
์ฐ์ ์์ ๋๊ธฐ์ด
์ฐ์ ์์ ๋๊ธฐ์ด์ ๊ฐ ์์๊ฐ ์ฐ์ ์์ ์ ์ฐ๊ฒฐ๋๊ณ ํด๋น ์ฐ์ ์์์ ๋ฐ๋ผ ๋ฐฐ์น๋๋ ํน๋ณํ ์ ํ์ ๋๊ธฐ์ด์ ๋๋ค . ์ต์ ํ์ ๋ ์ฝ๊ฒ ๊ตฌํํ๊ธฐ ์ํด Java์์ ์ ๊ณตํ๋ PriorityQueue ํด๋์ค java.util.PriorityQueue ๋ฅผ ์ฌ์ฉํฉ๋๋ค . ์ฃผ์ด์ง ์์๊ฐ ์ฐ์ ์์์ ์ ๋ ฌ/๋ฐฐ์น๋์ด์ผ ํ๋ ๊ฒฝ์ฐ ์ฐ์ ์์ ํ๊ฐ ์ฌ์ฉ๋ฉ๋๋ค. ์ฐ์ ์์ ๋๊ธฐ์ด์ ํ์ค ๋๊ธฐ์ด์ด FIFO(First-In-First-Out ) ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋ฅด๊ธฐ ๋๋ฌธ์ ๋จ์ํ ๋๊ธฐ์ด๊ณผ ๋ค๋ฆ ๋๋ค. ๊ทธ๋ฌ๋ ๋๋ก๋ ๋๊ธฐ์ด์ ์์๊ฐ ์ฐ์ ์์์ ๋ฐ๋ผ ์ฒ๋ฆฌ๋์ด์ผ ํ๊ธฐ ๋๋ฌธ์ ์ฐ์ ์์ ๋๊ธฐ์ด์ด ์ค๊ณ๋์์ต๋๋ค. ์ฐ์ ์์ ํ์ ์์๋ฅผ ์ถ๊ฐํ๋ฉด ๊ธฐ๋ณธ์ ์ผ๋ก ์ต์ ํ์ด ์์ฑ๋ฉ๋๋ค.๊ณตํต ์์
๊ตฌํ์ผ๋ก ์ด๋ํ๊ธฐ ์ ์ ์์์ผ ํ java.util.PriorityQueue ์ ๋ช ๊ฐ์ง ์ผ๋ฐ์ ์ธ ์์ ์ด ์์ต๋๋ค.- add(int ์์) ์ง์ ๋ ์์๋ฅผ ์ฐ์ ์์ ๋๊ธฐ์ด์ ์ฝ์ ํฉ๋๋ค.
- remove(int element)๋ ์ง์ ๋ ์์๊ฐ ์๋ ๊ฒฝ์ฐ ์ด ๋๊ธฐ์ด์์ ๋จ์ผ ์ธ์คํด์ค๋ฅผ ์ ๊ฑฐํฉ๋๋ค.
- peek() ๋ ์ด ๋๊ธฐ์ด์ ํค๋๋ฅผ ๊ฒ์ํ์ง๋ง ์ ๊ฑฐํ์ง๋ ์์ต๋๋ค. ๋๊ธฐ์ด์ด ๋น์ด ์์ผ๋ฉด null์ ๋ฐํํฉ๋๋ค.
- poll()์ ์ด ๋๊ธฐ์ด์ ํค๋๋ฅผ ๊ฒ์ ๋ฐ ์ ๊ฑฐํ๊ฑฐ๋ ์ด ๋๊ธฐ์ด์ด ๋น์ด ์์ผ๋ฉด null์ ๋ฐํํฉ๋๋ค.
- contains()๋ ์ด ๋๊ธฐ์ด์ ์ง์ ๋ ์์๊ฐ ํฌํจ๋์ด ์์ผ๋ฉด "true"๋ฅผ ๋ฐํํฉ๋๋ค.
- size()๋ ์ด ์ฐ์ ์์ ํ/์ต์ ํ์ ์์ ์๋ฅผ ๋ฐํํฉ๋๋ค.
์ฐ์ ์์ ๋๊ธฐ์ด์ ์ฌ์ฉํ์ฌ Java์์ ์ต์ ํ ๊ตฌํ
๋ค์์ Java์ ์ฐ์ ์์ ํ ํด๋์ค๋ฅผ ์ฌ์ฉํ์ฌ ์ต์ ํ์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ๋๋ค.
import java.util.*;
class MinHeapPriorityQueue {
static PriorityQueue minHeap = new PriorityQueue();
public static void view() {
for (Integer x : minHeap) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String args[]) {
// using "add" operation to insert elements
minHeap.add(3);
System.out.print("minHeap.add(3) = ");
view();
minHeap.add(13);
minHeap.add(7);
minHeap.add(16);
minHeap.add(21);
minHeap.add(12);
minHeap.add(9);
// printing Min-Heap
System.out.print("minHeap.view() = ");
view();
// using "peek" method to view the head
System.out.println("minHeap.peek() = " + minHeap.peek());
// using "poll" method to remove and retrieve the head
minHeap.poll();
System.out.print("minHeap.poll() = ");
view();
// using "remove" method to remove specified element
minHeap.remove(7);
System.out.print("minHeap.remove(7) = ");
view();
// Check if an element is present using contains()
boolean elementFound = minHeap.contains(11);
System.out.println("minHeap.contains(11) = " + elementFound);
elementFound = minHeap.contains(16);
System.out.println("minHeap.contains(16) = " + elementFound);
}
}
์ฐ์ถ
minHeap.add(3) = 3 minHeap.view() = 3 13 7 16 21 12 9 minHeap.peek() = 3 minHeap.poll() = 7 13 9 16 21 12 minHeap.remove(7) = 9 13 12 16 21 minHeap.contains(11) = ๊ฑฐ์ง minHeap.contains(16) = ์ฐธ
GO TO FULL VERSION