우선순위 큐

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오도록 하는 알고리즘

우선순위 큐(priority queue)란 FIFO의 특징을 가진 큐(queue)에 우선순위 방식을 접목시킨 자료구조입니다. 즉, 먼저 들어온 원소가 아닌 우선순위가 높은 원소가 먼저 나가는 특징을 가집니다. 우선순위 큐는 힙(heap)이라는 자료구조를 통해 구현할 수 있습니다. 그렇다면 힙은 무엇일까요?

힙(heap)이란 우선순위 큐를 위해 고안된 완전 이진트리 형태의 자료구조입니다. 트리에 대해 모르신다면, 뒤쪽의 트리 파트를 먼저 보시고 오시길 바랍니다.

힙의 종류에는

1️⃣ 최대 힙: 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진트리 2️⃣ 최소 힙: 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진트리

가 있습니다.

최대 힙이 default인 C++과는 다르게, python에서 힙은 최소 힙이 default입니다. 이는 뒤의 연습문제에서 다시 한 번 확인해보도록 하겠습니다.

힙은 앞서 배웠던 덱과는 다르게 모듈에서 자료구조 자체를 제공해주진 않습니다. 하지만 리스트를 힙처럼 사용할 수 있도록, 모듈에서 여러가지 함수를 제공합니다.

from heapq import heappush, heappop

대표적으로 heappush()와 heappop() 함수가 있습니다. 이름 그대로 heappush()는 원소 삽입시에, heappop()은 원소 삭제시에 사용하게 됩니다. 자세한 사용법을 알아봅시다.

heappush

from heapq import heappush
hq = []
heappush(hq, 4) # hq == [4]
heappush(hq, 2) # hq == [2, 4]
heappush(hq, 3) # hq == [2, 4, 3]
heappush(hq, 1) # hq == [1, 2, 3, 4]

위처럼 heappush(hq, 값)의 방식으로 힙에 요소를 삽입할 수 있습니다. 원소가 삽입되기만 하는 게 아니라, 삽입되면서 최소 힙으로 새롭게 힙 정렬되는 모습을 주석을 통해 확인할 수 있습니다. 백문이 불여일타 ! 😎 직접 hq를 조회하며 과정을 확인해보세요.

heappush할 때 어떻게 자동으로 정렬되는 것일까?

아래는 C++ 최대 힙 기준으로 [2,7,15,18,3,22,5]의 원소를 하나씩 넣는 과정에서 heapq가 새롭게 정렬되는 모습입니다. heapq는 한 원소를 넣을 때마다 O(logN)의 시간복잡도를 가지는 것을 알 수 있습니다. 이진트리를 이용해 정렬하는 과정이니 당연하겠죠? 비교와 조정의 과정에서 힙의 높이 O(logN) 만큼을 소요하는 것을 아래에서 확인할 수 있습니다.

heappop

from heapq import heappop
hq = [1, 2, 3, 4]
print(heappop(hq)) # 1 출력
print(hq)          # [2, 4, 3] 출력

삭제는 heappop(hq)의 방식으로 사용하면 됩니다. heappop()은 실행 시에 부모 노드의 값이 삭제되고, 그 값을 반환하게 됩니다.

heappush와 마찬가지로 삭제 시에도 최소 힙으로 새롭게 힙 정렬됩니다.

heappify

그렇다면 빈 리스트에 값을 하나씩 넣는(heappush) 작업 대신, 이미 원소가 정해진 리스트를 힙으로 바꿀 순 없을까요?

from heapq import heapify
hq = [4, 2, 3, 1]
heapify(hq)
print(hq)   # [1, 2, 3, 4] 출력

heapify()를 사용하면 위와 같이, 리스트 내부의 원소들이 힙 구조에 맞게 재배치됩니다. 이 때 heapify()는 모든 원소들을 새롭게 조정해야 하므로 O(N)의 시간복잡도를 가집니다.

연습문제

BOJ 1927

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

from heapq import heappush, heappop

n = int(input())
hq = []
for _ in range(n):
    val = int(input())
    if val != 0:
        heappush(hq, val)
        continue
    if not hq:
        print(0)
    else:
        print(heappop(hq))

위에서 언급했듯, python의 heapq 라이브러리는 최소 힙이 default입니다. 따라서 heapq에 집어넣으면 자동으로 최소힙으로 반환해주었습니다.

최대 힙은 우리가 직접 구현해야 할텐데요, heapq 라이브러리를 가지고 어떻게 응용할지 한 번 1분동안 생각해보세요.

BOJ 11279

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

from heapq import heappush, heappop

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

스스로 답변해보셨다면, 맞습니다 ! 모든 원소에 음수(-)를 취하면 됩니다. 이후 삭제 시에는 다시 음수를 취하면 기존의 값과 동일하게 출력할 수 있습니다.

from heapq import heappush, heappop

n = int(input())
hq = []
for _ in range(n):
    val = int(input())
    if val != 0:
        heappush(hq, [-val, val])
        continue
    if not hq:
        print(0)
    else:
        print(heappop(hq)[1])

값을 변화시켜서 삽입한 위의 방법과 달리, 값을 직접 수정하지 않는 방식도 있습니다. 앞의 방법과 거의 유사한데요, 삽입할 값으로 배열이 들어오면, heappush이 알아서 최소힙 정렬한다는 특징을 조금 더 이용해 봅시다.

2차원 배열 형태로 만들어 첫번째 index로 음수를 취한 값(-val)을, 두번째 index로는 우리가 원하는 값(val)을 할당하여 최소힙 정렬되도록 구현해줍니다. 우리는 꺼낸 값의 두번째 index를 사용하면 됩니다.

BOJ11286

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

from heapq import heappush, heappop

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

위 연습 문제의 두 번째 방법을 이해하셨다면, 이 문제는 어렵지 않게 풀 수 있습니다.

부모 노드가 자식 노드보다 작은 절댓값을 가져야 하므로, 0번 인덱스가 절댓값이고 1번 인덱스가 원래의 값인 배열을 하나씩 삽입해주면 됩니다. 절댓값 기준으로 힙 정렬될 수 있게 말이죠.

풀어볼 문제

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

[백준] 이중 우선순위 큐

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

[백준] 과제

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

[백준] 보석 도둑