[STL] Priority Queue(2) - Lazy Update

2025.3.10

 

1. Update / Erase (임의 원소의 변경, 삭제)

PQ는 주어진 push, pop 외에 다른 방식의 데이터 조작을 허용하지 않는다

= 중간 원소들에 접근이 불가능함. 

     -> 이를 위해서 추가적인 로직이 필요!

1) Lazy Update	2) Real - time Update
실시간으로 힙 내부를 최신화하지 않고 top을 구하는 과정에서 유효하지 않은 값을 버린다	실시간으로 PQ 내부를 최신화한다 이를 위해 내부의 원소 접근이 필요하며 STL PQ 사용 불가.
- 최신 정보를 저장하는 별도의 배열을 만들어 관리 - PQ가 실시간 업데이트 되지 않으므로 유효하지 않은 값들도 들어가있게 된다 (= size로 유효한거 찾기 어려움) - top을 확인할 때 유효하지 않은 값들은 버린다. 이때 판단은 우선순위 1개를 구하는지, 여러개를 구하는지에 따라 달라질 수 있다	- 각 원소들의 heap index를 기록하는 별도의 배열(pos[]) 필요 - heap의 위치가 swap 될 때마다 pos[] 배열도 같이 swap됨 - 특정 id의 value 값이 변경되거나 삭제될 때, pos[id]로 바뀐id의 heap index에 접근 - PQ에 push(), pop()외에 erase(), update() 기능을 추가해줘야하며 push(), pop()을 응용하여 구현 가능
주로 요 방법을 많이 사용함	STL PQ를 못쓰니까 직접 구현, logic생성도 필요함.

 

2. Lazy Update

원소가 삭제될 때	원소가 변경될 때
최신정보를 저장하는 배열에 삭제 되었음을 표시.  heap에는 아무 변화 없음.	최신정보를 저장하는 배열에 변경된 값을 기록.  heap에 변경된 정보를 push (기존 값은 그대로 둠)
우선순위 값 한개 확인할 때	우선순위 값 여러개 확인할 때
top에 있는 값이 유효한 정보인지 확인      => 최신 값과 일치하면 됨. 유효한 정보라면 처리하고 종료, 아니라면 pop() 한 뒤 다 반복	유효한 우선순위 값을 순차적으로 담을 배열을 생성하여 관리 top에 있는 값이 유효한 정보인지 확인      => 최신 값이랑 일치해야하고      직전에 뽑은 우선순위랑은 달라야함 (중복처리 조건 필요) 맞다면 배열에 담기 일괄적으로 pop()한 뒤 원하는 개수를 찾을 때까지 반복 다 구한 뒤에는 배열에 담은 값들을 pq에 다시 push()

 

EXAMPLE

- 초기설정

 

 

- 맨 처음 상태   S[id] = 최신 value 기록, 0이면 존재하지 않음. (요구하는 value의 범위 따라 숫자 변경) Pq는 max heap으로 구성 우선순위 기준은 (1)value 큰 순 (2) id 큰 순

 

- 삭제 및 변경

1번 삭제하기	5번의 value 3으로 변경하기
S[1]을 0으로 하여 삭제되었음을 표시한다 pq는 변화 없다.	S[5]를 3으로 하여 변경되었음을 표시한다. pq에 {id =5, value =3}을 push하여 최신정보를 등록한다 기존 노드인 {id =5, value =9}는 유효하지 않지만 pq에 남아있게 된다.

 

- 우선순위 값 1개 구하기

top node {id=5, value=9} 유효한지 확인 최신 value인 S[5]와 top의 value가 다르므로 유효하지 않다.  => pop()	top node {id=1, value=7} 유효한지 확인 최신 value인 S[1]와 top의 value가 다르므로 유효하지 않다.  => pop()	top node {id=2, value=4} 유효한지 확인 최신 value인 S[2]와 top의 value가 같으므로 유효하다 => 우선순위 값 확정! {2, 4}

 

- 우선순위 값 여러개 구하기

• 우선순위 값 3개를 구하는 방법
  • pq는 최우선순위 값을 빠르게 구할 수 있지만 3번째 값을 바로 구하지는 못함
  • *** pop해나가며 별도 배열에 기록해야함.
  • 그렇게 3개 값을 배열에 기록했으면 요구사항을 수행하고 다시 pq에 push로 돌려넣기

• 유효성 검증

초기상태에서 update{id =5, value =5}, update{id =5, value =9} 가 수행된 경우를 생각해보자! S[5] = 9, pq에는 id = 5인 node가 총 3개 등록되지만 이 중 하나만 최신정보가 된다. 유효성 검증을 할 때 단순 S[id] 하고만 비교하게 되면 2개가 유효하다고 판별된다. 우선순위 여러개를 구할 때 {5,9}는 한 개만 기록되어야한다 이를 위해 추가적으로 중복검사를 하는 것이 필요하다 직전에 유효하다고 기록한 정보가 top과 같으면 유효하지 않다고 판별하므로 {5,9} 가 한번만 기록될 수 있다.  = 직전의 정보와 동일한가만 판별. 동일하다면 무조건 연속해서 나오기 때문!! (pq의 특성)

중복검사 안하면 {5, 9}, {5, 9}, {1, 7} 이렇게 나옴. 이를 방지하기 위해 직전에 기록한거랑 비교하는 과정이 필요

중복검사를 실행하면 {5, 9}, {1, 7}, {2, 4} 이렇게 우선순위 3개 나옴

과정을 조금 더 자세히 살펴보자

	우선순위 값을 전부 구했으므로 필요한 동작 수행 후 전부 재등록!

 

 

3. Real-Time Update (나중에 따로 공부하기)