1927번 최소 힙

문제 출처 : https://www.acmicpc.net/problem/1927

우선순위 큐를 공부했으니 풀어보자 라는 생각으로 봤는데 최소 힙 문제가 나왔다.
간단하게 우선순위 큐에 대해 다시 짚어보자.

일반적인 큐는 선입선출의 방식으로 동작하나 우선순위 큐는 일반적인 큐와 다르게 요소들에 우선순위가 존재한다고 가정한다. ( ex. 응급실, 우선순위가 높을수록 먼저 작동한다. )
하지만 이런 우선순위 큐를 배열이나 연결리스트로 구현한다면 어떻게 될까?

배열

어떤 index의 요소에 접근하기 위해 O(1)이상의 연산을 요구하기 때문에 index가 많으면 많을수록 점 점 비효율적으로 작동한다.

연결리스트

마찬가지. 연결리스트는 삽입과 삭제에 있어 효율적일 뿐 값을 탐색한다면 배열과 마찬가지로 비효율적인 방식으로 작동한다.

그렇기 때문에 우선순위 큐는 힙을 자료구조로써 이용한다.

파이썬에서 힙을 어떻게 구현할까?

• 여기서 잠깐. 파이썬에 우선순위 큐가 지원이 되나 우선순위 큐는 힙으로 구현한다.

import heapq

파이썬에서 heapq는 내장모듈로써 기본적으로 힙의 구현을 지원하며 이때 힙은 기본적으로 최소 힙을 따른다. 또한 힙은 별도의 객체로서 새로 생성하는 게 아니라 리스트를 인자로 받아 그 자체로 힙으로 이용한다.

예시로 보자.

import heapq
heap = []

heapq.heappush(heap,2)
heapq.heappush(heap,1)
heapq.heappush(heap,6)
heapq.heappush(heap,4)
print(heap)

>>>[1,2,6,4]

heapq.heappop(heap)

>>>[2,4,6]

왜 [1,2,6,4]인가?

아주 중요한 부분인데 최소 힙은 가장 작은 값을 index=0 에 배치시키고 트리의 height 수준에서 대소를 비교할 뿐 형제 노드의 크기는 비교하지 않는다. 따라서 두번째 작은 값을 얻기 위해 heap[1]과 같이 접근하는 것을 잘못된 방식으로 가장 작은 원소의 삭제를 통해서 다음으로 작은 최소값에 접근할 수 있다.

왜 또 [2,4,6] 인가?

...파이썬에서 어떻게 힙이 동작하는지 공부할 필요가 있겠다..

import sys
import heapq

N = int(sys.stdin.readline().rstrip("\n"))
heap = []
for _ in range(N) :
    n = int(sys.stdin.readline().rstrip("\n"))
    if n!=0 :
        heapq.heappush(heap,n)
    else :
        if not heap :
            print("0")
        else :
            print(heapq.heappop(heap))

최대 힙 적용은 -를 붙여 최소로 판단하게끔 한다.

어디서 이렇게 시간차이가 나는 걸까 이렇게 시간차이가 날 만한 일인가?

아직 배우는 중이기 때문에 잘못된 부분이 있다면 귀엽게 봐주시고 가감없는 비판과 수정 감사드립니다