[BOJ] 1927번: 최소 힙 | 11279번: 최대 힙 | 11286번: 절댓값 힙

https://www.acmicpc.net/problem/1927

 

 

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

풀이

힙: 완전 이진트리 형태의 자료 구조로, 최소힙은 루트가 최솟값이고 최대힙은 루트가 최댓값이다.

 

삽입 과정: 완전 이진트리 조건을 만족하는 위치에 삽입 -> 부모 노드와 크기 비교 후 자리 확정

삭제 과정: 항상 루트 노드만을 삭제 (최소/최대 값 삭제) -> 새로운 루트 찾음 (가장 마지막 노드를 루트로 이동 -> 자식과 크기 비교하며 자리 확정)

*힙에서의 삽입, 삭제의 시간복잡도는 O(logn)

 

파이썬에서는 heapq 모듈을 사용하여 구현 가능함

 

#사용예시
from heapq import heappush, heappop
hq = []
heappush(hq, 4)
heappop(hq)

 

해당 문제에서도 적절한 조건문과 heappush, heappop을 사용하면 풀 수 있음. 다만 시간초과가 발생할 수 있음.

필자는 pypy3 + sys 조합으로 시간초과 해결...

 

input = __import__('sys').stdin.readline
from heapq import heappush, heappop
hq = []

for i in range(int(input())):
    x = int(input())
    if x:
        heappush(hq, x)
    else:
        print(0 if not hq else heappop(hq))

 

---

파이썬의 heapq는 디폴트가 최소힙이다! 따라서 최대힙의 경우에는 x에 -를 붙이면 된다.

  1                      -3

 /   \                    /   \

2   3               -1    -2

 

이런 느낌! 최소힙이지만 절댓값이 큰 수가 루트노드가 된다. 출력할 때도 -를 붙여서 출력하면 된다.

 

https://www.acmicpc.net/problem/11279

input = __import__('sys').stdin.readline
from heapq import heappush, heappop

hq = []
for _ in range(int(input())):
    x = int(input())
    if x:
        heappush(hq, -x) 
    else:
        print(0 if not hq else -heappop(hq))

 

---

https://www.acmicpc.net/problem/11286

 

절댓값 힙의 경우에는 리스트 단위로 힙에 삽입하는 방법이 있다. 

 

heappush(hq, [abs(val), val]) #튜플이나 리스트를 힙에 넣으면 첫 번째 요소를 기준으로 우선순위가 결정

 

0번째 원소를 절댓값을 취한 형태로 삽입을 하면, 절댓값을 기준으로 최소힙이 형성된다. 그 후 출력할 때는 뒷 원소를 이용하면 된다.

 

input = __import__('sys').stdin.readline
from heapq import heappush, heappop

hq = []
for _ in range(int(input())):
    x = int(input())
    if x:
        heappush(hq, [abs(x), x])
    else:
        print(0 if not hq else heappop(hq)[1])