์ฐ์ ์์ ํ์ ๊ฐ๋
์ฐ์ ์์ ํ(Priority Queue)๋ ์ถ์ ์๋ฃํ(Abstract Data Type, ADT) ์ค ํ๋๋ก, ๊ฐ ๋ฐ์ดํฐ์ ์ฐ์ ์์๋ฅผ ๋ถ์ฌํ์ฌ ์ฐ์ ์์์ ๋ฐ๋ผ ๋ฐ์ดํฐ๋ฅผ ์ฝ์ , ์ญ์ ํ๋ค. FIFO ์ ์ฑ ์ ๋ฐ๋ฅด๋ ์ผ๋ฐ์ ์ธ ํ์ ๋ฌ๋ฆฌ '์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ฐ์ดํฐ' ํน์ '์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๋ฐ์ดํฐ'๋ฅผ ์ฐ์ ์ ์ผ๋ก ์ฒ๋ฆฌํ๋ค.
์ถ์ ์๋ฃํ(Abstract Data Type, ADT)
๋ฉ๋ชจ๋ฆฌ์์ ๋ฐ์ดํฐ๋ฅผ ์ค์ ๋ก ์ ์ฅํ๋ ์๋ฃ๊ตฌ์กฐ์๋ ๋ฌ๋ฆฌ ๋ฐ์ดํฐ์ ๋ฐ์ดํฐ๋ฅผ ๋ค๋ฃจ๋ ์ฐ์ฐ(๋์)์ ์ ์ํ ๊ฐ๋ ์ผ๋ก, ๊ตฌํ ๋ฐฉ๋ฒ(How)์๋ ๊ด์ฌ์ ๋์ง ์๊ณ , ์ฌ์ฉ์๊ฐ ์ด๋ป๊ฒ ์ฌ์ฉํ ์ ์๋์ง(What)๋ง ์ ์ํ๋ ๋ฐฉ์์ด๋ค.
ํ์ ์คํ ๋ฑ๋ ์๋ฐํ ๋ฐ์ง๋ฉด ์๋ฃ๊ตฌ์กฐ๊ฐ ์๋๋ผ ์ถ์ ์๋ฃํ์ ํด๋นํ๋ค.
์ฐ์ ์์ ํ์ ์ฃผ์ ์ฐ์ฐ
- insert: ์๋ก์ด ๋ฐ์ดํฐ์ ํด๋น ๋ฐ์ดํฐ์ ์ฐ์ ์์๋ฅผ ํ์ ์ถ๊ฐํ๋ ์ฐ์ฐ
- delete: ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์/๋ฎ์ ๋ฐ์ดํฐ๋ฅผ ํ์์ ์ ๊ฑฐํ๋ ์ฐ์ฐ
- peek: ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์/๋ฎ์ ๋ฐ์ดํฐ๋ฅผ ์ ๊ฑฐํ์ง ์๊ณ ๋ฐํํ๋ ์ฐ์ฐ
ํ์ ๊ฐ๋
ํ(Heap)์ ์์ ์ด์ง ํธ๋ฆฌ ํํ๋ฅผ ๋ ๋ฉฐ, ํน์ฑํ ์์ ์์ฑ์ ๋ง์กฑํ๋ ์๋ฃ๊ตฌ์กฐ๋ค. ํ์๋ ์ต๋ ํ๊ณผ ์ต์ ํ์ ๋ ๊ฐ์ง ์ข ๋ฃ๊ฐ ์๋ค.
์ต๋ ํ๊ณผ ์ต์ ํ
์ต๋ ํ(Max Heap)
๋ถ๋ชจ ๋ ธ๋์ ๊ฐ์ด ์์ ๋ ธ๋์ ๊ฐ๋ณด๋ค ํญ์ ํฌ๊ฑฐ๋ ๊ฐ๋ค.
์ต์ ํ(Min Heap)
๋ถ๋ชจ ๋ ธ๋์ ๊ฐ์ด ์์ ๋ ธ๋์ ๊ฐ๋ณด๋ค ํญ์ ์๊ฑฐ๋ ๊ฐ๋ค.
ํ์ ์ฃผ์ ์ฐ์ฐ๊ณผ ์๊ฐ ๋ณต์ก๋
์๊ฐ๋ณต์ก๋์ ๊ฒฝ์ฐ ์์์ ๊ฐ์๊ฐ N๊ฐ์ธ ๊ฒฝ์ฐ๋ก ๊ฐ์ ํ์ฌ ์์ฑํ์๋ค.
์ฝ์
์๋ก์ด ์์๋ฅผ ์ถ๊ฐํ๊ณ , ํ ์์ฑ์ ์ ์งํ๊ธฐ ์ํด ์ํฅ ์กฐ์ (heapify-up)์ ์ํํ๋ค. ํ ํธ๋ฆฌ์ ๋์ด๊ฐ log N์ด๋ฏ๋ก ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ ๋ณต์ก๋๋ O(log N)์ด๋ค.
์ญ์
๋ฃจํธ ์์(์ต๋ ํน์ ์ต์)๋ฅผ ์ ๊ฑฐํ๊ณ , ๋ง์ง๋ง ์์๋ฅผ ๋ฃจํธ ๋ ธ๋๋ก ์ฎ๊ธด ํ ํํฅ ์กฐ์ (heapify-down)์ ํตํด ํ ์์ฑ์ ๋ณต์ํ๋ค. ์ด ๊ณผ์ ์ญ์ ํธ๋ฆฌ ๋์ด ๋งํผ์ ์๊ฐ์ด ์์๋๋ฏ๋ก ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ ๋ณต์ก๋๋ O(log N)์ด๋ค.
์ต๋/์ต์ ์์ ์ ๊ทผ
ํ์์๋ ๋ฃจํธ ๋ ธ๋์ ํญ์ ์ต๋(๋๋ ์ต์) ์์๊ฐ ์์นํ๋ฏ๋ก, ์ต๋/์ต์ ์์ O(1)๋ง์ ์ ๊ทผํ ์ ์๋ค.
ํ ๋น๋
์ฃผ์ด์ง ๋ฐฐ์ด์ ํ ๊ตฌ์กฐ๋ก ์ฌ๊ตฌ์ฑํ๋ ๊ณผ์ ์ผ๋ก, ์ผ๋ฐ์ ์ผ๋ก O(n) ์๊ฐ์ ๊ฐ๋ฅํ๋ค.
์ฐ์ ์์ ํ์ ํ
์์ ๋งํ๋ฏ, ์ฐ์ ์์ ํ๋ ์ถ์์๋ฃํ์ด๋ฉฐ, ์๋ฃ๊ตฌ์กฐ๊ฐ ์๋๋ค. ์ด๋ฌํ ์ฐ์ ์์ ํ๋ฅผ ๊ตฌํํ๊ธฐ ์ํด์ ๋ค์ํ ์๋ฃ๊ตฌ์กฐ(๊ท ํ ์ด์ง ๊ฒ์ ํธ๋ฆฌ, ํผ๋ณด๋์น ํ ๋ฑ)๋ฅผ ์ฌ์ฉํ ์ ์๋๋ฐ ๊ทธ ์ค ํ๋๊ฐ ํ์ธ ๊ฒ์ด๋ค. ์ฆ, ์ฐ์ ์์ ํ์ ํ์ ๋์ผํ ๊ฐ๋ ์ด ์๋๋ฉฐ, ํ์ ์ฐ์ ์์ ํ๋ฅผ ๊ตฌํํ๋ ๋ํ์ ์ธ ์๋ฃ๊ตฌ์กฐ๋ค.
ํ์ ์ฌ์ฉํ๋ฉด ์ฐ์ ์์ ํ์ ์ฝ์ ๊ณผ ์ญ์ ์ฐ์ฐ ๋ชจ๋ O(log N) ์๊ฐ์ ์ํํ ์ ์์ผ๋ฉฐ, ์ต๋/์ต์ ์์์ ๋ํ ์ ๊ทผ์ O(1) ์๊ฐ์ ๊ฐ๋ฅํด ๋งค์ฐ ํจ์จ์ ์ด๋ค. ์ด๋ฌํ ํจ์จ์ฑ ๋์ ํ์ด ์ฐ์ ์์ ํ๋ฅผ ๊ตฌํํ๋ ๋ํ์ ์ธ ์๋ฃ๊ตฌ์กฐ๊ฐ ๋ ๊ฒ์ด๋ค.
์ฐ์ ์์ ํ์ ์ฅ์ ๊ณผ ๋จ์
์ฅ์
- ์ฐ์ ์์ ํ๋ ํญ์ ์ต์ฐ์ ์์ ์์์ ๋น ๋ฅด๊ฒ ์ ๊ทผํ ์ ์๋ค.
- ์์ ์ค์ผ์ค๋ง, ๊ทธ๋ํ ์๊ณ ๋ฆฌ์ฆ(ex. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ), ์ด๋ฒคํธ ์๋ฎฌ๋ ์ด์ ๋ฑ ์์ฉ ๋ถ์ผ๊ฐ ๋ค์ํ๋ค.
- ํ ์ธ์๋ ๋ค์ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด ์ฐ์ ์์ ํ๋ฅผ ์ ์ฐํ๊ฒ ๊ตฌํํ ์ ์๋ค.
๋จ์
- ์ฐ์ ์์ ํ๋ ํน์ ์์๋๋ก ์ ๋ ฌ๋ ์ ์ฒด ๋ฐ์ดํฐ๋ฅผ ํ์ํ๊ธฐ ์ด๋ ค์, ์์ฐจ์ ์ผ๋ก ์ ๊ทผํ ํ์๊ฐ ์๋ ๊ฒฝ์ฐ์๋ ๋ถ์ ํฉํ๋ค.
- ํ์ด๋ ๋ค๋ฅธ ํจ์จ์ ๊ตฌํ ๋ฐฉ์์ ์ฝ๋๊ฐ ๋ณต์กํด์ง ์ ์๋ค.
์ฐ์ ์์ ํ์ ์ฌ์ฉ ์ฌ๋ก
- ๋์ ์ฐ์ ์์์ ๋ฐ๋ผ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํด์ผ ํ๋ ๊ฒฝ์ฐ
- ๊ฐ ๋จ๊ณ๋ง๋ค ์ต๋๊ฐ ๋๋ ์ต์๊ฐ์ ์ ํํ๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(ex. ๋ค์ต์คํธ๋ผ ์ต๋จ ๊ฒฝ๋ก, ํ๋ฆผ ์ต์ ์ ์ฅ ํธ๋ฆฌ)
- ๋คํธ์ํฌ ๋ผ์ฐํ , ์์ ์ค์ผ์ค๋ง ๋ฑ์์ ๊ฐ ์์ ์ ์ฐ์ ์์์ ๋ฐ๋ผ ์ฒ๋ฆฌํ ๋
- ์ค์๊ฐ ๋๋ ์ด๋ฒคํธ๋ฅผ ์๊ฐ์ ํน์ ์ฐ์ ์์์ ๋ฐ๋ผ ์ฒ๋ฆฌํด์ผ ํ ๋
- ์ด๋ฒคํธ ์๋ฎฌ๋ ์ด์ ์์ ๋ค์์ ๋ฐ์ํ ์ด๋ฒคํธ๋ฅผ ๋น ๋ฅด๊ฒ ์ฐพ์๋ด์ ์ฒ๋ฆฌ
- ์๋ฎฌ๋ ์ด์ ์์คํ , ๊ฒ์ ์์ง์์ ์ด๋ฒคํธ ํ ๊ด๋ฆฌ ๋ฑ
- ๋ฌธ์ ํด๊ฒฐ ๊ณผ์ ์์ ํ์ฌ ๊ฐ์ฅ ์ค์ํ ์ ํ์ ๋ฐ๋ณต์ ์ผ๋ก ๊ฒฐ์ ํด์ผ ํ ๋
- A* ์๊ณ ๋ฆฌ์ฆ์์ ์ฐ์ ์์ ํ๋ฅผ ํ์ฉํด ์ถ์ ๋น์ฉ์ด ๊ฐ์ฅ ๋ฎ์ ๊ฒฝ๋ก๋ฅผ ์ ํ
ํ์ ์ฌ์ฉํ ์ฐ์ ์์ ํ(Python)
Python์ ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ์๋ heapq
๋ชจ๋์ด ํฌํจ๋์ด ์์ด, ์ต์ ํ ๊ธฐ๋ฐ์ ์ฐ์ ์์ ํ๋ฅผ ์ฝ๊ฒ ๊ตฌํํ ์ ์๋ค.
heapq ๋ชจ๋์ ์ฃผ์ ํจ์
heapq.heappush(heap, item)
: ํ์ ์์๋ฅผ ์ฝ์ ํ๋ค.heapq.heappop(heap)
: ํ์์ ๊ฐ์ฅ ์์ ์์๋ฅผ ์ ๊ฑฐํ๊ณ ๋ฐํํ๋ค.heapq.heapify(x)
: ์ผ๋ฐ ๋ฆฌ์คํธ๋ฅผ ํ ๊ตฌ์กฐ๋ก ๋ณํํ๋ค.
๊ตฌํ ์์
import heapq
data = [6, 5, 7, 4, 9, 1, 3]
# heapify๋ฅผ ์ฌ์ฉํ์ฌ ๋ฆฌ์คํธ๋ฅผ ํ์ผ๋ก ๋ณํ
heapq.heapify(data)
print("ํ ์ด๊ธฐ ์ํ:", data) #์ต์ ํ์ด๋ฏ๋ก ๋ฃจํธ์ ์ต์๊ฐ์ด ์์น
# ์์ ์ถ๊ฐ
heapq.heappush(data, 2)
print("์์ ์ถ๊ฐ ํ ์ํ:", data)
# ๊ฐ์ฅ ์์ ์์ ์ ๊ฑฐ
smallest = heapq.heappop(data)
print("์ ๊ฑฐ๋ ์ต์ ์์:", smallest)
print("์ต์ ์์ ์ ๊ฑฐ ํ ์ํ:", data)