지연 삽입/삭제

Question

우선 순위 대기열을 편집하고 (다른 것들 중에서도) 삽입 기능을 구현하는 임무가 있습니다. 나의 책은 "게으른 삭제"와 "게으른"의미를 결코 지정하지 않는 다른 게으른 행동을 언급하고 있지만.

짧게 : 삽입/삭제 기능과 LAZY 삽입/삭제 기능의 차이점은 무엇입니까?

Answer 1

"지연 제거"는 대개 직접 삭제하는 대신 삭제 한 항목을 표시하고 표시된 항목이없는 것처럼 보이는 다른 작업을 수정하는 것을 의미합니다.

우선 순위 대기열의 경우 예를 들어 중간에서 적극적으로 제거하는 대신 대기열 해제 절차에서 삭제 된 항목을 뛰어 넘을 수 있습니다.

마찬가지로 "지연 삽입 (lazy insert)"은 요소를 입력 대기열에 추가 할 수 있습니다. 이는 일정 시간 작동입니다. 일반적으로 우선 순위 대기열에 삽입하려면 O (log n) 시간이 필요합니다. 대기열에서 제외하려고하면 입력 대기열이 우선 순위 대기열로 플러시됩니다. 이것은 디큐 동작까지 삽입 연산의 비용을 줄이는 효과가 있습니다.

기본적으로 "게으른"은 결과가 필요할 때까지 작동하지 않는 것을 의미합니다.