1. ์ ์ ๐โ๏ธ
ํ์ ๋ ฌ์ด๋ ์๋ฃ๊ตฌ์กฐ ํ(Heap)์ ๊ธฐ๋ฐ์ผ๋ก ํ๋ ์ ๋ ฌ ๋ฐฉ์์ด๋ค. ์ค๋ฆ์ฐจ์ ์ ๋ ฌ์ผ ๊ฒฝ์ฐ ์ต๋ํ์ ์ด์ฉํ๊ณ ๋ด๋ฆผ์ฐจ์ ์ ๋ ฌ์ผ ๊ฒฝ์ฐ ์ต์ํ์ ์ด์ฉํ๋ค.
๊ฐ๋จํ๊ฒ ์ค๋ช ํ์๋ฉด ํ ์ ๋ ฌ์ ๋ฃจํธ๋ ธ๋๋ฅผ ์ ๊ฑฐํ๊ณ ์ ๊ฑฐ๋ ๋ฃจํธ ๋ ธ๋๋ฅผ ๋ฐฐ์ด์ ๋ท๋ถ๋ถ๋ถํฐ ์ฑ์ ๋ฃ์ผ๋ฉด์ ์ ๋ ฌ์ด ์ด๋ฃจ์ด์ง๋ ๊ฒ์ด๋ค.
2. ๋์ ๋ฐฉ์ ๐ฃโ๏ธ
์ต๋ํ์ ์ด์ฉํ์ฌ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ณด์. ๊ฐ์ฅ ์ฝ๊ฒ ์๊ฐํ ์ ์๋ ๋์๋ฐฉ์์ ์๋์ ๊ฐ๋ค.
- ์ ๋ ฌํด์ผ ํ๋ ์์๋ค์ ํ๋์ฉ ํ์ ๋ฃ์ด์ค๋ค.
- ์ญ์ ๋ฅผ ํ๋ฉด์ ๋ฃจํธ ๋ ธ๋๋ฅผ ๊ฐ์ ธ์ค๊ณ ๊ทธ๊ฒ์ ๋ฐฐ์ด์ ๋ท๋ถ๋ถ๋ถํฐ ์ฑ์ด๋ค.
์ด๋ ๊ฒ ํ๋ค๋ฉด ๊ธฐ์กด ๋ฐฐ์ด๋ก๋ถํฐ ํ์ ๊ตฌ์ฑํ๋ ๋ฐฐ์ด ํ๋๋ฅผ ์ถ๊ฐ์ ์ผ๋ก ๋ง๋ค๊ณ (1๋ฒ ๊ณผ์ ), ๋ท๋ถ๋ถ๋ถํฐ ์ ๋ ฌ๋ ์์๋ค์ ๋ฃ์ ๋ฐฐ์ด์ ํ๋ ๋ ๋ง๋ค์ด์ผ ํ๋ค.(2๋ฒ ๊ณผ์ ) ๊ทธ๋ฌ๋ฉด ์ด 2๊ฐ์ ๋ฐฐ์ด์ ๋ ๋ง๋ค์ด์ผ ํ๋ ๋ฌธ์ ๊ฐ ์๋ค.
๊ทธ๋ฌ๋ฏ๋ก ๊ธฐ์กด์ ๋ฐฐ์ด์์ ๋ฐ๋ก ์ ๋ ฌํ ์ ์๋ ๋ฐฉ์์ ์์๋ณด์. ์ด ๋ฐฉ์์ Heapify ์ฐ์ฐ์ ์ด์ฉํ์ฌ ์ถ๊ฐ ๋ฐฐ์ด์ ์์ฑํ์ง ์๊ณ ์ ๋ ฌํ๋ค. Heapify๋ ํ ์์ฑ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋ถ๋ชจ ๋ ธ๋์ ๋ ์์ ๋ ธ๋ ์ค ํฌ๊ธฐ๊ฐ ๋ ํฐ ์์์ ๋ถ๋ชจ์ ๋ฐ๊พธ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋์ ๋ฐฉ์์ ์๋์ ๊ฐ๋ค.
- ์ต๋ ํ์ ๊ตฌ์ฑํ๋ค.
- ๋ฃจํธ ๋ ธ๋๋ฅผ ๋ง์ง๋ง ์์์ ๋ฐ๊พผ๋ค.
- ํ์ ์ฌ์ด์ฆ๋ฅผ ํ๋ ์ค์ด๊ณ ํ์ ๋ค์ ๊ตฌ์ฑํ๋ค.
- 2~3 ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
์ผ๋ฐ์ ์ธ ๋ฐฐ์ด์ ๊ฒฝ์ฐ 0๋ฒ ์ธ๋ฑ์ค๋ถํฐ ์์ํ๋ฏ๋ก ๋ถ๋ชจ ์ธ๋ฑ์ค์ ์์ ์ธ๋ฑ์ค์ ๊ด๊ณ๋ฅผ ์๋์ ๊ฐ์ด ์๊ฐํ๋ค๋ ์ ์ ์ ์ํ์.
๋ถ๋ชจ Index = (์์ Index) / 2 - 1
์ผ์ชฝ ์์ Index = (๋ถ๋ชจ Index) * 2 + 1
์ค๋ฅธ์ชฝ ์์ Index = (๋ถ๋ชจ Index) * 2 + 2
'2, 1, 3, 4, 5'๋ฅผ ํ์ ๋ ฌ์ ์ด์ฉํด์ ์ ๋ ฌํด ๋ณด์. size๋ 5์ด๋ฏ๋ก 1๋ถํฐ ๋ถ๋ชจ์ธ๋ฑ์ค๋ก ํ์ฌ ์ต๋ํ์ ๊ตฌ์ฑํ๋ค. ( 5 / 2 - 1 = 5)(์ฝ๋์์ ๊ตฌํ๋ Heapify๋ฅผ ์ฐธ๊ณ ํ๋ฉด ๋์ ๋ฐฉ์ ์ถฉ๋ถํ ์ดํดํ ์ ์์ ๊ฒ์ด๋ค. ์ฐ์ ๊ทธ๋ฆผ์ ํตํด ๋์ ๋ฐฉ์์ ํฌ๊ฒ ์ดํดํด ๋ณด๋๋ก ํ์.)
์์ฑ๋ ๋ชจ์ต์ ์๋์ ๊ฐ๋ค.
๊ทธ๋ฆฌ๊ณ ๋ฃจํธ ๋ ธ๋์ ๋ง์ง๋ง ์์๋ฅผ ๋ฐ๊ฟ์ฃผ๊ณ ํ์ ์ฌ๊ตฌ์ฑํ๋ ๋์์ ๋ฐ๋ณตํ๋ค. ๊ทธ๋ฌ๋ฉด ๋ง์ง๋ง ๋ ธ๋๋ถํฐ ํด์ ์์๋ค์ด ์ ๋ ฌ๋๋ค. ์ ๋ ฌ๋ ์์๋ ํ๋์์ผ๋ก ํ์ํ์๋ค.
์ต์ข ์ ์ผ๋ก ์ ๋ ฌ๋ ๋ชจ์ต์ ์๋์ ๊ฐ๋ค.
3. ๊ตฌํ(JAVA) ๐โ๏ธ
๋ค์์ ๊ตฌํ์ฝ๋์ด๋ค. Heapify๊ฐ ๊ธฐ๋ณธ์ ์ผ๋ก ๋์ํ๋ ๋ฐฉ์๊ณผ ์ฌ์ด์ฆ๋ฅผ ์ค์ฌ๊ฐ๋ฉด์ Heapify๋ฅผ ํธ์ถํ๋ ๋ฐฉ์์ ์ ์ํด์ ์ฝ๋๋ฅผ ์ดํดํด ๋ณด์.
public static void main(String[] args) {
int[] array = { 2,1,3,4,5 };
heapSort(array);
}
public static void heapSort(int[] array) {
int size = array.length;
// ํ์ ๊ตฌ์ฑํ๋ค. - ๋์๋ฐฉ์(1)
int parent = size / 2 - 1;
for(int i = parent; i >= 0; i--) {
heapify(array, size, i);
}
for(int i = size - 1; i > 0; i--) {
// ๋ฃจํธ๋
ธ๋์ ๋ง์ง๋ง ์์๋ฅผ ๋ฐ๊พผ๋ค. - ๋์๋ฐฉ์(2)
swap(array, 0, i);
// ํ์ ์ฌ์ด์ฆ๋ฅผ ํ๋ ์ค์ด๊ณ ํ์ ๋ค์ ๊ตฌ์ฑํ๋ค. - ๋์๋ฐฉ์(3)
heapify(array, i, 0);
}
}
public static void heapify(int array[], int size, int current) {
int parent = current;
int leftChild = current * 2 + 1;
int rightChild = current * 2 + 2;
if(leftChild < size
&& array[parent] < array[leftChild]) {
parent = leftChild;
}
if(rightChild < size
&& array[parent] < array[rightChild]) {
parent = rightChild;
}
if(current != parent) {
swap(array, parent, current);
heapify(array, size, parent);
}
}
public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
4. ์๊ฐ๋ณต์ก๋ ๐คฝโ๏ธ
Heapify๋ฅผ ํ๋๋ฐ ์๊ฐ๋ณต์ก๋๋ O(log N)์ด๋ค. ํ ์ ๋ ฌ์ ํ๋๋ฐ Heapify๋ฅผ N๋ฒ ํธ์ถํด์ผ ํ๋ฏ๋ก ์ด ์๊ฐ๋ณต์ก๋๋ O(N logN)์ด ๋๊ฒ ๋๋ค.
์ต์ (BEST) | ํ๊ท (AVERAGE) | ์ต์ (WORST) | |
์๊ฐ๋ณต์ก๋ | O(N logN) | O(N logN) | O(N logN) |
ํด๋น ๊ธ์
Gyoogle๋์ ํ ์ ๋ ฌ(Heap Sort),
๋๋๋น๋์ ํ ์ ๋ ฌ(Heap Sort)
์ ์ฐธ๊ณ ํ์์ต๋๋ค.
'๐ ์๋ฃ๊ตฌ์กฐ > ์ ๋ ฌ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์นด์ดํ ์ ๋ ฌ (Counting Sort) (0) | 2023.04.12 |
---|---|
ํต ์ ๋ ฌ (Quick Sort) (0) | 2023.03.20 |
์์ ์ ๋ ฌ(Topology Sort) (2) | 2023.03.07 |
๋ณํฉ ์ ๋ ฌ(Merge Sort) (0) | 2023.03.07 |
์ฝ์ ์ ๋ ฌ(Insertion Sort) (0) | 2023.03.06 |