1. ์ ์ ๐ณ
ํ(Heap)์ด๋ ์ฌ๋ฌ ๊ฐ๋ค ์ค ์ต๋๊ฐ ํน์ ์ต์๊ฐ์ ๋น ๋ฅด๊ฒ ์ฐพ์๋ด๊ธฐ ์ํ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
ํ์ ํน์ง
- ์์ ์ด์งํธ๋ฆฌ์ ์ผ์ข ์ด๋ค.
- ๋ฐ์ ๋ ฌ ์ํ์ด๋ค.
์ต๋ํ(Max Heap) ๋๋ ์ต์ํ(Min Heap)์ ๋ฐ๋ผ์ ๋ฃจํธ ๋ ธ๋๊ฐ ํญ์ ๊ฐ์ฅ ํฐ ๊ฐ์ด๊ฑฐ๋ ๊ฐ์ฅ ์์ ๊ฐ์ ์ ์งํ๊ธฐ ๋๋ฌธ์ด๋ค. - ์ค๋ณต๋ ๊ฐ์ ํ์ฉํ๋ค.
ํ์ ์ข ๋ฅ
- ์ต๋ ํ (Max Heap)
๋ถ๋ชจ ๋ ธ๋์ ํค ๊ฐ์ด ์์ ๋ ธ๋์ ํค ๊ฐ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ์์ ์ด์งํธ๋ฆฌ ํ์ - ์ต์ ํ (Min Heap)
๋ถ๋ชจ ๋ ธ๋์ ํค ๊ฐ์ด ์์ ๋ ธ๋์ ํค ๊ฐ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ์ด์งํธ๋ฆฌ ํ์
2. ๋์ ๋ฐฉ์ ๐
์ธ๋ฑ์ค | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
๊ฐ | - | 9 | 7 | 6 | 4 | 5 | 1 | 3 | 8 |
Heap์ ๋ฐฐ์ด์ ํตํด ์ฝ๊ฒ ๊ตฌํ์ด ๊ฐ๋ฅํ๋ค. ๊ทธ ์ด์ ๋ ํ์ด ์์ ์ด์งํธ๋ฆฌ์ด๊ธฐ ๋๋ฌธ์ ๋ฐฐ์ด์ ๊ฐ์ ์์๋๋ก ๋ฃ์ผ๋ฉด์ ๊ตฌํํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
๋ถ๋ชจ Index = (์์ Index) / 2
์ผ์ชฝ ์์ Index = (๋ถ๋ชจ Index) * 2
์ค๋ฅธ์ชฝ ์์ Index = (๋ถ๋ชจ Index) * 2 + 1
์ธ๋ฑ์ค ๋ฒํธ๋ฅผ ํ์ฉํ์ฌ '๋ถ๋ชจ ๋ ธ๋์ ์์ ๋ ธ๋์ ์ฝ๊ฒ ์ ๊ทผํ ์ ์๋ค. ์์ ๊ฐ์ ์ฌ์ด ์ ๊ทผ ๋ฐฉ์์ ์ํด 0๋ฒ ์ธ๋ฑ์ค๋ ์ฌ์ฉํ์ง ์๋๋ค.
Heap์ '์ฝ์ ๋ฐฉ์'๊ณผ '์ญ์ ๋ฐฉ์'์ ํตํด ํ์ ๋์ ๋ฐฉ์์ ์์๋ณด์.
1. ์ฝ์
์ฝ์ ์ ๋ค์๊ณผ ๊ฐ์ ์์๋ก ์ด๋ฃจ์ด์ง๋ค.
- ์๋ก์ด ๋
ธ๋๋ฅผ ํ์ ๋ง์ง๋ง ๋
ธ๋์ ์ด์ด์ ์ฝ์
ํ๋ค.
๋ฐฐ์ด์ ๋ง์ง๋ง์ ์์๋ฅผ ์ถ๊ฐํ๋ค. - ์๋ก์ด ๋
ธ๋๋ฅผ ๋ถ๋ชจ ๋
ธ๋์ ๋น๊ตํ๋ฉด์ ๊ตํ์ ํ๋ค.
์ต๋ ํ์ ๊ฒฝ์ฐ, ์ถ๊ฐํ ๊ฐ์ด ๋ถ๋ชจ ๋ ธ๋๋ณด๋ค ํฌ๋ฉด ์๋ฆฌ๋ฅผ ๋ฐ๊พผ๋ค.
์ต์ ํ์ ๊ฒฝ์ฐ, ์ถ๊ฐํ ๊ฐ์ด ๋ถ๋ชจ ๋ ธ๋๋ณด๋ค ์์ผ๋ฉด ์๋ฆฌ๋ฅผ ๋ฐ๊พผ๋ค. - 2๋ฒ์ ๋ฐ๋ณตํ๋ค.
์ต๋ ํ์์์ ์ฝ์ ์ ๊ทธ๋ฆผ์ ํตํด ์ดํด๋ณด์.
7๋ฒ ์ธ๋ฑ์ค๊น์ง ์๋ ์ต๋ํ์ 8์ด๋ผ๋ ์ซ์๋ฅผ ์ฝ์ ํด ๋ณด์. ์์ ๋์๋ฐฉ์๊ณผ ์๋์ ๊ทธ๋ฆผ์ ํ๋ฆ์ ์ ๋ฐ๋ผ๊ฐ๋ค๋ฉด ์ดํด๋ฅผ ํ๋๋ฐ ํฐ ๋ฌด๋ฆฌ๊ฐ ์์ ๊ฑฐ๋ผ๊ณ ์๊ฐํ๋ค.
์์ฑ๋ ๋ชจ์ต์ ์๋์ ๊ฐ๋ค.
2. ์ญ์
ํ์์์ ์ญ์ ๋ ๋ฃจํธ ๋ ธ๋๋ฅผ ์ญ์ ํ๋ ๊ฒ์ด๋ค. ๋ง์ฝ ์ต๋ํ์ด๋ผ๋ฉด ์ต๋๊ฐ์ ์ญ์ ํ๋ ๊ฒ์ด๊ณ ์ต์ํ์ด๋ผ๋ฉด ์ต์๊ฐ์ ์ญ์ ํ๋ ๊ฒ์ด๋ค. ๋ฐฉ์์ ์๋์ ๊ฐ๋ค.
- ๋ฃจํธ๋ ธ๋์์ ๊ฐ์ ์ ๊ฑฐํ๋ค.
- ๋ง์ง๋ง ๋ ธ๋๋ฅผ ๋ฃจํธ ๋ ธ๋๋ก ์ฎ๊ธด๋ค.
- ์์ ๋
ธ๋์ ๋์๊ด๊ณ๋ฅผ ๋น๊ตํ๋ค.
์ต๋ ํ์ ๊ฒฝ์ฐ, ์์ ๋ ธ๋ ์ค์์ ๋ ํฐ ๋ ธ๋์ ๋ถ๋ชจ ๋ ธ๋์ ์๋ฆฌ๋ฅผ ๋ฐ๊พผ๋ค.
์ต์ ํ์ ๊ฒฝ์ฐ, ์์ ๋ ธ๋ ์ค์์ ๋ ์์ ๋ ธ๋์ ๋ถ๋ชจ ๋ ธ๋์ ์๋ฆฌ๋ฅผ ๋ฐ๊พผ๋ค. - 3๋ฒ์ ๋ฐ๋ณตํ๋ค.
์ต๋ํ์์์ ์ญ์ ๋ฅผ ๊ทธ๋ฆผ์ ํตํด ์ดํด๋ณด์. 11๋ฒ ์ธ๋ฑ์ค๊น์ง ์๋ ์ต๋ํ์์ ์ญ์ ๊ฐ ์ด๋ฃจ์ด์ง๋ค๊ณ ํ์. ์ด๊ฒ ๋ํ ๋์ ๋ฐฉ์๊ณผ ๊ทธ๋ฆผ์ ํ๋ฆ์ ์ ๋ฐ๋ผ๊ฐ๋ค๋ฉด ์ดํด๋ฅผ ํ๋๋ฐ ํฐ ๋ฌด๋ฆฌ๊ฐ ์์ ๊ฑฐ๋ผ๊ณ ์๊ฐ๋๋ค.
์์ฑ๋ ๋ชจ์ต์ ์๋์ ๊ฐ๋ค.
3. ๊ตฌํ(JAVA) ๐ฌ
์ฝ์ ๊ณผ ์ญ์ ์์์ ๋์ ๋ฐฉ์์ ๊ธฐ๋ฐ์ผ๋ก ์ฝ๋๋ฅผ ์ดํด๋ณด์.
1. ์ฝ์
static void insert_max_heap(int x) {
// ๋ง์ง๋ง ๋
ธ๋์ ์์ x๋ฅผ ์ถ๊ฐ
maxHeap[++heapSize] = x;
for(int i = heapSize; i > 1; i /= 2) {
// ์์๋
ธ๋๊ฐ ๋ถ๋ชจ๋
ธ๋๋ณด๋ค ๋ ํฐ ๊ฒฝ์ฐ ์๋ฆฌ ๊ตํ
if(maxHeap[i / 2] < maxHeap[i]) {
swap(i / 2, i);
}
else {
break;
}
}
}
2. ์ญ์
static int delete_max_heap() {
// ๋ฐฐ์ด์ด ๋น์ด์๋ ๊ฒฝ์ฐ
if(heapSize == 0)
return -1;
//์ญ์ ํ ๋
ธ๋ ์ ์ฅ(๋ฆฌํด์ ์ํ ๊ฒ)
int item = maxHeap[1];
// ๋ง์ง๋ง ๋
ธ๋๋ฅผ ๋ฃจํธ ๋
ธ๋๋ก ์ฎ๊ธด๋ค.
maxHeap[1] = maxHeap[heapSize];
maxHeap[heapSize--] = 0;
for(int i = 1; i * 2 <= heapSize;) {
// ๋ง์ง๋ง ๋
ธ๋๊ฐ ์์ ๋
ธ๋๋ค๋ณด๋ค ๋ ํฐ ๊ฒฝ์ฐ
if(maxHeap[i] > maxHeap[i * 2]
&& maxHeap[i] > maxHeap[i * 2 + 1]) {
break;
}
// ์ผ์ชฝ ๋
ธ๋๊ฐ ๋ ํฐ ๊ฒฝ์ฐ
else if(maxHeap[i * 2] > maxHeap[i * 2 + 1]) {
swap(i, i * 2);
i = i * 2;
}
// ์ค๋ฅธ์ชฝ ๋
ธ๋๊ฐ ๋ ํฐ ๊ฒฝ์ฐ
else {
swap(i, i * 2 + 1);
i = i * 2 + 1;
}
}
return item;
}
ํด๋น ๊ธ์
์ฝ๋ ์ฐ๊ตฌ์์ '[์๋ฃ๊ตฌ์กฐ]Max Heap, Min Heap, Heap ์ด๋? | C์ธ์ด Heap ๊ตฌํ',
Passwd๋์ '์ต์ ํ/ ์ต๋ ํ',
Gyoogle๋์ 'ํ(Heap)'
์ ์ฐธ๊ณ ํ์์ต๋๋ค.
'๐ ์๋ฃ๊ตฌ์กฐ > ํธ๋ฆฌ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ธ๊ทธ๋จผํธ ํธ๋ฆฌ(Segment Tree) (0) | 2023.04.13 |
---|