우선순위 큐 내부 구조체 연산자 오버로딩 ( Priority_Queue , Struct , Operator Overloading)

구현 할때마다 헷갈리는 우선순위 큐를 사용할 때 ,

자료형이 구조체인 경우 정렬을 위한 연산자 오버로딩을 정리해보려고합니다. 

 

우선순위 큐 안에 기본적인 int 형 자료형이 들어가면 내림차순으로 정렬되어 들어갑니다. (내부적으로 heap(디폴트로 Max_heap)으로 구현되어있기때문입니다.)

 

이런 간단한 구조에서는 쉽지만, 만약 여러 값들을 갖는 구조체가 자료형으로 우선순위 큐 안에 들어가게되면

어떤 값을 기준으로 정렬을 해야 할 지 모르기때문에, 그 기준을 정해주어야 합니다. 그 기준을 정하는 방법은

구조체 내부에서 < 연산자 오버로딩을 통해 가능합니다.

 

Pos라는 구조체 내부에서 연산자 오버로딩을 해주면 , PQ에 push를 할 때 연산자 오버로딩의 정의에 맞추어 정렬하게 됩니다.

 

저 부등호 방향때문에 골머리를 앓았습니다. 왜냐하면 vector 안에 구조체가 들어갔을때는 우선순위 큐와 반대로 정렬되기 때문입니다 ㅜㅜ

 

벡터에서 사용할때를 기준으로 보면 위의 오버로딩 내에 return y < pos1.y만 있다고 가정하면 오름차순으로 저장됩니다. 기존의 y와 추가로 push되는 새로운pos1.y와 비교하여 만약 기존에 벡터에 있던 y가 더컸을때는 false를 반환하여 자리를 swap하는거죠. 새로들어온 pos1.y가 더 컸다면 true를 반환하고 swap을 하지않고 그대로 두는겁니다.

(사실 내부적으로 정확히 어떻게 구현되어 정렬해주는지는 잘 모르겠습니다 제 예상으로는 저렇게 한번 정렬한후 다시 또 인접 인덱스값들끼리 비교하여 전체적으로 다시 최종 정렬을 할 것 같습니다.. 아시는 분 계시면 알려주시면 감사하겠습니다 ㅜㅜ )

 

 

이제 중요합니다.

우선순위 큐안에서는 return y < pos1.y가 y값을 기준으로 내림차순으로 정렬하게 됩니다.

 

그 이유는 여기서의 y는 PQ의 루트값(가장 앞의 값)으로 기준을두고 새로 들어오는 pos1.y와 비교를합니다.

만약 pos1.y가 크다면 true를 반환하고 true일때 우선순위가 크다고 판단하여 루트노드의 데이터와 자리를 교체합니다.

결국 계속해서 들어오는 y의 값에 따라 제일 큰 값이 앞에오는 내림차순이 됩니다.

 

반대로 밑에 줄의 x >pos1.x 같은 경우에는 루트값의 x값이 새로 들어온 pos1.x의 값보다 클때 true를 리턴하고 결국

새로들어오는 x값이 작을 때가 우선순위가 높다고 판단하여 x값이 작을 수록 앞에 위치하게 되는겁니다. 

(이 역시 틀린 정보일 수 있습니다. 스스로 공부하면서 이해한 내용을 적는것이니 틀린부분은 언제든지 지적해주세요)

 

그래서 결국 (3,4) (3,5) (4,7)이 PQ에 저장되어 있는 순서는

처음 3,4와 3,5는 x값이 같기 때문에 y < pos1.y를 따르고 우선순위 큐이기 때문에 y값이 더클수록 우선순위가 높아 앞에위치하게 되어 (3,5) (3,4) 순으로 저장되고 (4,7)이 들어오면 x값이 다르기때문에 x>pos1.x의 조건을 따라 (3,5) 와 (4,7)을 비교하여 3보다 4가 더 크기때문에 false를 반환하고 swap이 일어나지 않아 최종적으로 (3,5) (3,4) (4,7) 순서로 저장됩니다.

 

 

 

 

 

@ 혼자 공부한 내용을 복습겸 적은 것이기 때문에 , 틀린부분이 많을 수 있습니다 ! 

잘못된 부분 댓글로 정정해주시면 정말 감사하겠습니다.