Numbering

Priority Queue Undo Trick

도입 어떤 자료구조 $D$에 대해 다음 세 연산을 지원해야 하는 상황을 생각해 보자. Push(u, p): 우선순위 $p$를 가진 업데이트 $u$를 $D$에 적용한다. Pop: 현재 $D$에 적용된 업데이트 중 우선순위가 가장 높은 것을 취소한다(undo). Query: $D$에 쿼리를 수행한다. 이 연산들의 조합은 표준 우선순위 큐와 비슷해 보이지만, 핵심 차이는 $D$에 대한 undo를 지원해야 한다는 점이다. 만약 Pop이 항상 가장 최근에 적용한 업데이트를 취소한다면 단순한 스택 + rollback으로 해결된다. Pop이 FIFO 순서라면 이 블로그에 소개된 Queue-like Undoing Trick으로...