python 우선순위 큐

    
 파이썬에서 우선순위 큐를 사용하는 방법은 여러 가지가 있지만, 대표적으로 `heapq` 모듈을 사용하는 방법이 있습니다. `heapq`는 최소 힙(min-heap)으로 동작하며, 이 힙을 사용하여 우선순위 큐를 구현할 수 있습니다.

### 기본 사용법: `heapq` 모듈

`heapq` 모듈은 리스트를 힙처럼 다룰 수 있도록 해주는 함수들을 제공합니다. 이 모듈을 이용하면 우선순위 큐를 쉽게 구현할 수 있습니다.

#### 1. 힙에 원소 추가하기: `heapq.heappush()`

```python
import heapq

# 빈 리스트를 힙으로 사용
heap = []

# 힙에 값 추가 (우선순위 큐에 삽입)
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heap)  # [1, 10, 5] -> 항상 최소값이 맨 앞에 있음
```

#### 2. 힙에서 원소 꺼내기: `heapq.heappop()`

```python
# 가장 작은 값 꺼내기 (우선순위가 가장 높은 값 제거)
smallest = heapq.heappop(heap)
print(smallest)  # 1
print(heap)      # [5, 10]
```

#### 3. 힙에서 최소값 확인 (제거하지 않음): `heap[0]`

```python
# 최소값 확인 (제거하지 않음)
min_value = heap[0]
print(min_value)  # 5
```

### 우선순위 큐에 튜플 사용하기

우선순위 큐에서 각 요소에 우선순위를 부여하고 싶다면, (우선순위, 값) 형태의 튜플을 힙에 삽입할 수 있습니다. 튜플의 첫 번째 요소를 기준으로 우선순위가 결정됩니다.

```python
import heapq

pq = []

# 우선순위가 낮은 순서대로 정렬됨 (1이 가장 높은 우선순위)
heapq.heappush(pq, (1, "작업 1"))
heapq.heappush(pq, (3, "작업 3"))
heapq.heappush(pq, (2, "작업 2"))

# 우선순위가 가장 높은 작업부터 꺼내기
while pq:
    priority, task = heapq.heappop(pq)
    print(f"우선순위 {priority}: {task}")
```

이 코드를 실행하면 다음과 같이 출력됩니다:
```
우선순위 1: 작업 1
우선순위 2: 작업 2
우선순위 3: 작업 3
```

### 최대 힙 구현

`heapq` 모듈은 기본적으로 최소 힙을 제공하지만, 최대 힙을 구현하려면 간단한 트릭을 사용하면 됩니다. 우선순위 값을 음수로 변환하여 힙에 삽입하면 최대값이 우선순위가 가장 높은 것처럼 동작하게 됩니다.

```python
import heapq

max_heap = []

# 음수로 변환해서 삽입
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)

# 값을 꺼낼 때 다시 음수로 변환
print(-heapq.heappop(max_heap))  # 10
print(-heapq.heappop(max_heap))  # 5
print(-heapq.heappop(max_heap))  # 1
```

이렇게 하면 우선순위가 가장 높은 값을 우선적으로 처리하는 최대 힙을 구현할 수 있습니다.

### 결론

- 파이썬에서 우선순위 큐를 구현할 때는 `heapq` 모듈을 사용하여 최소 힙을 만들 수 있습니다.
- (우선순위, 값) 형태의 튜플을 사용하면 다양한 우선순위를 가진 데이터를 처리할 수 있습니다.
- 최대 힙이 필요하다면 우선순위를 음수로 변환하여 처리할 수 있습니다.

이 방법을 사용해 다익스트라 알고리즘 같은 우선순위가 중요한 문제들을 해결할 수 있습니다!


파이썬의 `heapq` 모듈은 기본적으로 튜플의 첫 번째 요소를 기준으로 우선순위를 정렬합니다. 하지만 두 번째 요소를 우선순위로 사용하고 싶다면, 튜플의 순서를 바꾸는 방식으로 처리할 수 있습니다. 즉, (우선순위, 값) 대신 (값, 우선순위)로 튜플을 만들어서 우선순위를 제어하는 것이죠.

### 두 번째 요소를 우선순위로 사용하는 방법

우선순위를 나타내는 요소를 튜플의 첫 번째 위치로 변경한 후 `heapq`에 삽입하면, `heapq`는 두 번째 요소를 우선순위로 인식하게 됩니다.

예를 들어:

```python
import heapq

pq = []

# 값 대신 우선순위를 첫 번째로 배치
heapq.heappush(pq, ("작업 1", 1))
heapq.heappush(pq, ("작업 3", 3))
heapq.heappush(pq, ("작업 2", 2))

# 우선순위가 가장 낮은 순서대로 값이 출력됨
while pq:
    task, priority = heapq.heappop(pq)
    print(f"우선순위 {priority}: {task}")
```

이 코드를 실행하면 다음과 같이 출력됩니다:

```
우선순위 1: 작업 1
우선순위 2: 작업 2
우선순위 3: 작업 3
```

이 방법은 우선순위를 두 번째 요소로 사용하고 싶을 때 간단하게 적용할 수 있습니다.

### 만약 더 복잡한 기준이 필요하다면?

만약 우선순위를 비교할 때 두 번째 요소 외에도 여러 요소를 기준으로 복잡한 우선순위를 지정해야 한다면, 파이썬의 `functools` 모듈의 `cmp_to_key`를 이용해 복잡한 비교 함수를 정의할 수 있지만, 간단한 튜플 재배치로 많은 경우 해결할 수 있습니다.

이 방식으로 원하는 대로 우선순위를 지정할 수 있습니다!