우선순위 큐 안정성

우선순위 큐 안정성 기준

우선순위 큐는 가장 높은 우선순위 원소를 빠르게 꺼내지만, 내부 원소의 우선순위를 임의로 바꾸는 기능을 기본으로 제공하지 않는 경우가 많습니다. 비교 키, 동률 처리, lazy deletion 정책을 정해야 실전 문제가 안정됩니다.

01

비교 기준을 튜플 생성

우선순위, 삽입 순번, id처럼 비교 순서를 명확히 하면 동률 결과가 흔들리지 않습니다.

comparator
02

변경 연산 설계

기존 원소의 priority를 바꾸기 어렵다면 새 값을 넣고 꺼낼 때 최신 여부를 검사합니다.

lazy
03

stale entry를 버린다

Dijkstra처럼 더 짧은 거리가 나중에 들어오면 오래된 항목은 pop 시점에 무시합니다.

stale
04

안정성이 필요한지 판단한다

같은 priority의 FIFO 순서가 필요하면 삽입 카운터를 tie breaker로 둡니다.

stable
Comparator
엄격하고 일관된 순서를 만들어야 함 비교 결과가 상황에 따라 바뀌면 힙 불변식이 깨집니다.
order
Lazy deletion
삭제 대신 최신성 검사를 pop 시점으로 미룸 메모리는 더 쓰지만 구현이 단순하고 decrease-key 대체로 자주 씁니다.
practical
Tie breaker
동률에서 예측 가능한 결과 보장 삽입 순번을 함께 넣으면 안정 큐처럼 동작시킬 수 있습니다.
tie

최신성 검사 · 비교 키 수정 · 동률 테스트 점검

최신성 검사 pop한 항목이 현재 기록과 다른 오래된 값이면 버립니다.
비교 키 수정 힙 안에 있는 객체의 우선순위를 직접 바꾸면 재정렬되지 않을 수 있습니다.
동률 테스트 같은 priority 원소 여러 개를 넣어 출력 순서가 문제 요구와 맞는지 확인합니다.