> For the complete documentation index, see [llms.txt](https://koalas-organization.gitbook.io/koala_codingtest_study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koalas-organization.gitbook.io/koala_codingtest_study/data_structure/priority_queue.md).

# 우선순위 큐

**우선순위 큐(priority queue)**&#xB780; FIFO의 특징을 가진 큐(queue)에 <mark style="background-color:yellow;">**우선순위**</mark> 방식을 접목시킨 자료구조입니다.\
즉, 먼저 들어온 원소가 아닌 **우선순위가 높은 원소가 먼저 나가는** 특징을 가집니다.\
우선순위 큐는 힙(heap)이라는 자료구조를 통해 구현할 수 있습니다. 그렇다면 힙은 무엇일까요?

**힙(heap)**&#xC774;란 우선순위 큐를 위해 고안된 <mark style="background-color:yellow;">**완전 이진트리**</mark> 형태의 자료구조입니다. 트리에 대해 모르신다면, 뒤쪽의 트리 파트를 먼저 보시고 오시길 바랍니다.

힙의 종류에는

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

가 있습니다.

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

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

```python
from heapq import heappush, heappop
```

대표적으로 **heappush()**&#xC640; **heappop()** 함수가 있습니다. 이름 그대로 **heappush()**&#xB294; 원소 삽입시에, **heappop()**&#xC740; 원소 삭제시에 사용하게 됩니다. 자세한 사용법을 알아봅시다.&#x20;

## heappush

```python
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]
```

위처럼 <mark style="background-color:yellow;">**heappush(hq, 값)**</mark>의 방식으로 힙에 요소를 삽입할 수 있습니다.\
원소가 삽입되기만 하는 게 아니라, 삽입되면서 <mark style="background-color:yellow;">**최소 힙**</mark><mark style="background-color:yellow;">으로 새롭게 힙 정렬</mark>되는 모습을 주석을 통해 확인할 수 있습니다.\
백문이 불여일타 ! 😎 직접 hq를 조회하며 과정을 확인해보세요.&#x20;

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

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

<figure><img src="/files/puVg4vTvxAR431wQlV9J" alt=""><figcaption></figcaption></figure>

## heappop

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

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

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

## heappify

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

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

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

## 연습문제

### BOJ 1927

{% embed url="<https://www.acmicpc.net/problem/1927>" %}

```python
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

{% embed url="<https://www.acmicpc.net/problem/11279>" %}

```python
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))
```

스스로 답변해보셨다면, 맞습니다 ! <mark style="background-color:yellow;">**모든 원소에 음수(-)를 취하면**</mark> 됩니다. 이후 삭제 시에는 다시 음수를 취하면 기존의 값과 동일하게 출력할 수 있습니다.

```python
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를 사용하면 됩니다.&#x20;

### BOJ11286

{% embed url="<https://www.acmicpc.net/problem/11286>" %}

```python
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번 인덱스가 원래의 값인 배열을 하나씩 삽입해주면 됩니다. 절댓값 기준으로 힙 정렬될 수 있게 말이죠.

## 풀어볼 문제

{% embed url="<https://www.acmicpc.net/problem/7662>" %}
\[백준] 이중 우선순위 큐
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/13904>" %}
\[백준] 과제
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/1202>" %}
\[백준] 보석 도둑
{% endembed %}