https://www.acmicpc.net/problem/11286
백준 11286번 절댓값 힙

문제 파악

1. 문제 제목처럼 힙을 사용하면 될 것
2. 파이썬 내부 라이브러리 heapq 사용
3. 절댓값을 정렬 기준으로 해주기 -> 파이썬의 heapq는 최소 힙만 지원하기 때문에 최대 힙을 구현할 때 사용하는 방식을 활용하면 될 것 같음

코드

import heapq
from sys import stdin

input = stdin.readline

n = int(input())
h = []
heapq.heapify(h)
for _ in range(n):
    x = int(input())
    if x == 0:
        if not h:
            print(0)
        else:
            tmp = heapq.heappop(h)
            print(tmp[1])

    else:
        heapq.heappush(h, (abs(x), x))

1. h라는 힙을 선언
2. n번 반복하면서
3. x를 입력받기
4. x가 0이라면
5. 그리고 그때 h가 비었는지에 따라 분기

TIL

✅heapq에서 데이터가 비교 불가능한 경우라면?(e.g. 리스트, 딕셔너리, 클래스)
해결책

• 우선순위 외에 추가로 요소를 카운트하는 값을 추가해서 3개의 요소가 담긴 리스트로 (우선순위, 카운터, 데이터) 저장한다. 이렇게 되면 카운터는 같을 수 없기 때문에 입력된 순서대로 정렬되는 것이 보장된다.
  (e.g. class A, class B, class C가 순서대로 저장되고 각각 우선순위가 1, 2, 2라고 한다면 heapq에는
  (1, 1, class A)
  (2, 2, class B)
  (2, 3, class C)
  가 저장되는 것

• 데이터를 비교하지 않게 wapper class를 생성.
  공식 문서에서의 예제 코드

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

하지만 와닿지 않아서 GPT한테 예제코드를 작성해달라고 했다.

import heapq
from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any = field(compare=False)

# 우선순위 큐 생성 (빈 리스트)
priority_queue = []

# 몇 가지 작업 추가
heapq.heappush(priority_queue, PrioritizedItem(priority=1, item="중요한 작업"))
heapq.heappush(priority_queue, PrioritizedItem(priority=5, item="보통 작업"))
heapq.heappush(priority_queue, PrioritizedItem(priority=10, item="높은 우선순위 작업"))

# 우선순위 순으로 작업을 꺼내고 출력
while priority_queue:
    item = heapq.heappop(priority_queue)
    print(f"우선순위: {item.priority}, 항목: {item.item}")

설명에서 Prioritized Item이 우선순위 비교가 불가능한 데이터 그 자체를 설명한 것이었다.

✅ 책에서는 heapq 말고 priority queue를 사용했다.
둘 다 priority queue 알고리즘을 지원하는 라이브러리다. 이 둘의 차이는 멀티쓰레드 환경에서 동기화 문제에 있다.

hepq : 리스트를 기반으로 한 이진트리이다.

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero.

queue.priorityqueue : heapq를 기반으로 구현된 추상화된 인터페이스. 멀티쓰레드 환경에서 동기화를 보장한다.

The queue module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads. The Queue class in this module implements all the required locking semantics. It depends on the availability of thread support in Python; see the threading module.