
๐heapq๋?
๊ฐ๋จํ๊ฒ ๋ฆฌ์คํธ๋ด์์ ๊ฐ์ฅ ์์ ๊ฐ์ด ๋งจ์ฒ์์์น(์ธ๋ฑ์ค 0)์ ์ค๊ฒ ํด์ฃผ๋ ๋ด์ฅ ๋ชจ๋
์ฐ์ ์์ ํ๋ผ๊ณ ์๋ฉด ์ฝ๋ค.
๐ต ์์ํ๊ธฐ
import heapq
๐ต ์ ์ธํ๊ธฐ
๋ณดํต ๋ฆฌ์คํธ๋ฅผ ์ ์ธํ๋ ๊ฒ์ฒ๋ผ ๋ง๋ ๋ค.
heap_list = []
๐ต ์์ ์ถ๊ฐํ๊ธฐ ( heapq.heappush(๋ฆฌ์คํธ, ๊ฐ ))
- ์๋ ๋ณด์ด๋ ๊ฒ ์ฒ๋ผ ๊ฐ์ฅ ์์ ๊ฐ์ด ๋งจ ์ฒ์ ์์น์ ์๋ค.
์๊ฐ๋ณต์ก๋ O(logn)
heapq.heappush(heap_list, 5)
heapq.heappush(heap_list, 10)
heapq.heappush(heap_list, 99)
heapq.heappush(heap_list, 2)
print(heap_list) # [2, 5, 99, 10]
๐ต ์์ ์ญ์ ํ๊ธฐ ( heapq.heappop(๋ฆฌ์คํธ) )
- ์ ์ผ ์ฒ์์ ์๋ ๊ฐ์ด ์ญ์ ๋๋ฉด์ ๊ทธ ๊ฐ์ ๋ฆฌํดํ๋ค. ๊ฐ์ ์ญ์ ํ๊ณ ๋ค์ ์ถ๋ ฅํด๋ณด๋ ํ์ด ์ ๋ ฌ ๋์ด ์๋ค.
์๊ฐ๋ณต์ก๋ O(logn)
print(heapq.heappop(heap_list)) # [2, 5, 99, 10]
print(heap_list) # [5, 10, 99]
a = heapq.heappop(heap_list)
print(a) # 5
๐ต ๊ธฐ์กด์ ๋ฆฌ์คํธ๋ฅผ ํ์ผ๋ก ๋ณํํ๊ธฐ ( heapq.heapify(๋ฆฌ์คํธ) )
์๊ฐ๋ณต์ก๋ O(n)
ano_list = [9, 8, 7, 6, 5, 4, 1, 2, 5]
heapq.heapify(ano_list)
print(ano_list) # [1, 2, 4, 5, 5, 9, 7, 6, 8]
๐ต ์ต๋๊ฐ ๊ตฌํ๊ธฐ! (์์ฉ)
- ๊ฐ๋ค์ ํํ ํํ๋ก ๋ฃ์ด์ค๋ค. ํํํํ๋ก ๋ฃ์ด์ฃผ๋ฉด ํํ์ 0๋ฒ์งธ ์ธ๋ฑ์ค๋ฅผ ๊ธฐ์ค์ผ๋ก ํ์ ๋ ฌ์ด ๋๋ค.
numbers = [1,5,9,3,7,6,4,2,8]
max_list = []
for number in numbers:
heapq.heappush(max_list, (-number, number)) # ( ์ฐ์ ์์, -๋ฅผ ๋ถ์ด๋ฉด ๊ฐ์ฅ ํฐ ๊ฐ์ด ๊ฐ์ฅ ์์์ง๋ค. ์ค์ ๊ฐ)
while max_list:
print(heapq.heappop(max_list)[1])
'Programming language > Python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[python] filter (2) | 2020.08.31 |
---|---|
[python] accumulate(itertools), ๋์ ํฉ (0) | 2020.08.30 |
[python] defaultdict (0) | 2020.08.29 |
[python] pow, ์ ๊ณฑ, ๊ฑฐ๋ญ์ ๊ณฑ๊ณผ ๋๋จธ์ง (0) | 2020.08.28 |
[python] input, sys.stdin.readline (0) | 2020.08.27 |