heapq에서 우선순위가 같은 작업은 입력 순서로 나오나

heapq는 최소 항목부터 꺼내는 힙 연산을 제공합니다. 같은 우선순위 항목을 넣은 순서대로 반환한다는 안정성은 기본으로 보장하지 않습니다. (priority, task) 튜플에서는 priority가 같으면 다음 task 필드가 비교될 수 있습니다.

동점에서도 입력 순서를 유지하려면 (priority, sequence, task)처럼 증가하는 sequence를 중간 필드에 넣습니다. sequence가 다르면 task 객체끼리 비교하지 않아도 됩니다.

힙의 우선순위와 삽입 순서는 다른 기준입니다

heapq의 기본 힙은 가장 작은 항목을 먼저 꺼내는 min-heap입니다. 우선순위 큐를 만들 때 보통 (priority, task) 튜플을 저장하지만, 우선순위가 같을 때 삽입 순서로 반환된다고 기대하면 안 됩니다. Python 3.12 공식 문서는 동점 우선순위에서 안정성을 얻는 문제를 별도로 다루고, entry count를 tie-breaker로 추가하는 방법을 제안합니다. 우선순위 값이 낮은 항목을 먼저 처리하는지 높은 항목을 먼저 처리하는지도 프로그램이 선택한 표현에 달려 있습니다.

두 필드 튜플은 task 이름까지 비교합니다

먼저 우선순위가 모두 2인 write 작업과 audit 작업을 넣어 보겠습니다. Python의 튜플 비교는 앞 필드가 같으면 다음으로 다른 필드에서 순서를 정합니다. 두 작업 이름은 문자열이므로 task 필드의 사전식 순서가 적용되어 audit가 먼저 나올 수 있습니다. 즉 결과가 입력 순서와 달라집니다. task가 서로 순서 비교를 지원하지 않는 사용자 객체라면 같은 우선순위에서 비교를 시도하다 TypeError가 날 수도 있습니다.

from heapq import heappop, heappush

heap = []
heappush(heap, (2, "write"))
heappush(heap, (2, "audit"))
print([heappop(heap)[1] for _ in range(len(heap))])

위 코드의 출력은 ['audit', 'write']입니다. 이것은 heapq가 문자열 task를 특별히 알파벳순 정렬해서가 아니라, 튜플 비교가 같은 priority 다음 필드까지 비교하기 때문입니다. 반대로 task 객체가 정렬 불가능하면 오류가 날 수 있습니다. 실제 우선순위 큐에서는 task 내용이 우선순위 동점을 해결해야 할 의미 있는 기준이 아니라면 task 필드를 직접 비교하게 두지 않는 편이 안전합니다.

sequence를 동점 전용 비교 기준으로 넣습니다

각 항목을 넣을 때마다 고유한 순번을 발급해 priority 다음에 저장하면 됩니다. 이 순번은 두 작업의 priority가 같을 때 먼저 넣은 쪽이 더 작은 값을 가지도록 증가해야 합니다. tuple 비교는 (priority, sequence, task) 순서로 진행하므로 동점이면 sequence가 결정하고 task까지 가지 않습니다. 아래 예시는 itertools.count()로 0부터 증가하는 값을 만들며, 같은 우선순위 작업의 삽입 차례를 pop 결과에 반영합니다.

from heapq import heappop, heappush
from itertools import count

sequence = count()
heap = []
heappush(heap, (2, next(sequence), "write"))
heappush(heap, (2, next(sequence), "audit"))
print([heappop(heap)[2] for _ in range(len(heap))])

1. 먼저 우선순위의 크고 작음이 무엇을 뜻하는지 정합니다.
2. 같은 우선순위에서 입력 순서를 보존해야 하는지 결정합니다.
3. 보존이 필요하면 삽입마다 고유하고 증가하는 sequence를 만듭니다.
4. 힙 항목을 (priority, sequence, task)로 저장합니다.
5. pop 결과는 task 필드를 꺼내고 동점·다른 우선순위를 각각 확인합니다.

sequence는 단순 장식이 아니라 튜플 비교에서 task 필드로 넘어가지 않게 하는 기준입니다. 여러 생산자가 동시에 항목을 넣는 프로그램이라면 sequence를 생성하는 부분도 적절히 동기화해야 합니다. 이번 학습 예제는 한 실행 흐름에서 순차적으로 삽입하는 경우만 다룹니다. 우선순위 변경이나 취소된 항목의 삭제는 heap 불변식을 깨뜨릴 수 있으므로 다른 설계가 필요하며 이 글의 범위에서는 제외합니다.

heapq와 안정 정렬의 계약을 섞지 않습니다

정렬 함수가 같은 키의 기존 순서를 보존한다고 해서 힙도 같은 동점 규칙을 자동 제공한다고 생각하는 것이 흔한 오해입니다. Python 문서의 heapq 설명은 우선순위 큐에서 동점 작업 순서를 얻는 문제를 별도로 제기하고, 순번을 포함하는 해결책을 제시합니다. 따라서 heapify나 heappush를 사용했다는 사실만으로 입력 FIFO 순서를 추정하지 마세요. 자료구조가 제공하는 우선순위 기준과 프로그램이 추가한 동점 기준을 구별해야 합니다.

문제에서 항목이 정수처럼 비교 가능한 값이라면 priority가 같을 때 다음 요소가 어떤 값인지 확인하세요. 서로 다른 문자열 task라면 문자열 순서가 결과에 영향을 주고, 비교 불가능한 task라면 예외 가능성을 점검합니다. task를 비교하지 않으면서 입력 순서를 유지하고 싶다면 고유 sequence를 넣습니다. 이 방법은 heapq 공식 문서의 priority queue implementation notes가 제시하는 패턴과 같습니다.