[Algorithms] 스택,큐,해쉬,힙-최소힙 & 최대힙

 

 

 

 

• 윤성우 자료구조에서 배웠던대로 힙에 데이터를 넣고 빼는 과정은 이렇다

 

 

 

 

• 이것이 파이썬에서는 heapq 라이브러리로 아주 쉽게 구현이 된다

import sys
import heapq as hq  # heap 불러오기
 
 
# sys.stdin = open("input", "rt")
 
a=[]                # heap을 사용하려면 빈 리스트가 있어야 한다
while True:
    n=int(input())
    if n==-1:
        break
    elif n==0:
        if len(a)==0:
            print(-1)
        else:
            print(hq.heappop(a))   # heapq 에서 heappop은 루트 노드 값을 pop
    else:
        hq.heappush(a, n)          # heapq`에서 heappush는 heap에 값을 넣어준다
 
 

• 최대힙은 거의 유사하다. heapq가 기본적으로 최소힙을 기준으로 동작하니 최대힙이 되려면 -를 붙여서 작동이 되게끔 하면 된다

import sys
import heapq as hq  # heap 불러오기
 
a=[]                
while True:
    n=int(input())
    if n==-1:
        break
    elif n==0:
        if len(a)==0:
            print(-1)
        else:
            print(-hq.heappop(a))   # 출력되는 값에 -를 붙여준다
    else:
        hq.heappush(a, -n)          # 입력되는 값에 -를 붙여준다