#min heap(์ต์ ํ)์์ ๊ฐ์ฅ ์์๊ฐ์ ์ธ์ ๋ ์ธ๋ฑ์ค 0, ์ฆ, ์ด์ง ํธ๋ฆฌ์ ๋ฃจํธ์ ์์น
# 1 ---> root
# / \
# 3 5
# / \ /
# 4 8 7
#heapq ๋ชจ๋์ ์ด์ง ํธ๋ฆฌ(binary tree) ๊ธฐ๋ฐ์ ์ต์ ํ(min heap) ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ๊ณต
#heqpq๋ชจ๋์ ํ์ด์ฌ์ ๋ณดํต ๋ฆฌ์คํธ๋ฅผ ๋ง์น ์ต์ ํ์ฒ๋ผ ๋ค๋ฃฐ ์ ์๋๋ก ๋์์ค. ๋ณ๊ฐ์ ์๋ฃ๊ตฌ์กฐ X
#ํ์ด์ฌ์์๋ heapq ๋ชจ๋์ ํตํด์ ์์๋ฅผ ์ถ๊ฐํ๊ฑฐ๋ ์ญ์ ํ ๋ฆฌ์คํธ๊ฐ ๊ทธ๋ฅ ์ต์ ํ์ด ๋จ.
import heapq
a = [] #ํ์ด์ฌ์ ์ผ๋ฐ์ ์ธ ๋ฆฌ์คํธ ์ ์ธ
heapq.heappush(a, 6) #๋ฆฌ์คํธ๋ฅผ ์ธ์๋ก ๋๊ฒจ ์์๋ฅผ ์ถ๊ฐ
heapq.heappush(a, 1)
heapq.heappush(a, 4)
heapq.heappush(a, 5)
print(a) #[1, 5, 4, 6]
print(heapq.heappop(a)) #๋ฆฌ์คํธ๋ฅผ ์ธ์๋ก ๋๊ฒจ ์์๋ฅผ ์ญ์ . 1 ์ถ๋ ฅ ๋จ.
print(heapq.heappop(a)) #4 ์ถ๋ ฅ
print(a[0]) #์ ๊ฑฐํ์ง ์๊ณ ์ต์๊ฐ 5์ถ๋ ฅ, ๊ทธ ์ ์ heapq๋ชจ๋์ ํจ์๋ฅผ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ ๊ฐ์ฅ ์์ ๊ฐ์ด 0์ธ๋ฑ์ค์ ์ค๋๋ก ์ ๋ ฌ๋์ด ์์.
print(a) #[5, 6]
#----------------------------------------------------#
#heapq.heappop() ์ฃผ์ํ ์
#์ ์ผ ์์ ์๋ ์์ ์ ๊ฑฐํ๊ณ ํ ๊ตฌ์กฐ๋ก ๋ง๋ฌ
c = [6, 8, 4, 1]
print(c) #[6, 8, 4, 1]
print(heapq.heappop(c)) #6
print(c) #[1, 8, 4]
print(heapq.heappop(c)) #1
print(c) #[4, 8]
print(heapq.heappop(c)) #4
print(c) #[8]
print(heapq.heappop(c)) #8
#----------------------------------------------------#
#ํ ๊ตฌ์กฐ๋ก ์ฌ๋ฐฐ์น
b = [4, 1, 7, 3, 8, 5]
heapq.heapify(b) #ํ ๊ตฌ์กฐ์ ๋ง๊ฒ b๊ฐ ์ฌ๋ฐฐ์น ๋จ
print(b)
#์ต๋ ํ -------------------------------------------
import heapq
nums = [4, 1, 7, 3, 8, 5]
max_heap = []
for num in nums:
heapq.heappush(max_heap, (-num, num))
while max_heap:
print(heapq.heappop(max_heap)[1]) # ์ถ๋ ฅ
# 8
# 7
# 5
# 4
# 3
# 1
# K๋ฒ์งธ ์ต์๊ฐ ------------------------------------------
def k_min_val(list, k):
heapq.heapify(list) #์ต์ ํ ๊ตฌ์กฐ๋ก ์ฌ๋ฐฐ์น
for _ in range(k): #heappop์ k๋ฒ ๋ฐ๋ณต
min = heapq.heappop(list)
return min
a = [8,3,7,5,6]
print(k_min_val(a, 3)) #6์ถ๋ ฅ
#ํ ์ ๋ ฌ ------------------------------------------------
def sort_heap(list):
nums = []
for i in list: # ์ด ๋ถ๋ถ heapq.heapify()๋ก ๋์ฒด ๊ฐ๋ฅ
heapq.heappush(nums, i)
sorted_nums = []
while nums:
sorted_nums.append(heapq.heappop(nums))
return sorted_nums
b = [8,3,7,5,6]
print(sort_heap(b)) #[3, 5, 6, 7, 8]