[C++/priority_queue/operator overloading] 우선순위 큐 struct 연산자 오버로딩

priority_queue는 기본적으로 max_heap을 가지고 있다.

 

max_heap

 

어떻게 넣던간에 max_heap으로 저장이 되고 pop()할 때 마다 가장 큰 값이 나온다.

 

그런데 문제는 priority_queue(이하 pQ)안에 int형이 아닌 구조체나 클래스가 들어갈 수도 있는 것이고

여기서 우리가 정렬하고 싶은 방법이 있을 수 있다는 것

(예를 들면, x,y,z를 갖고 있는 구조체를 pQ에 넣을 때, z의 크기를 기준으로 heap을 만들고 싶다)

그럴 땐, 이와 같이 코드를 작성한다.

---

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;

struct Object {
	int x;
	int y;
	int z;

	Object(int a, int b,int c)
	{
		x = a;
		y = b;
		z = c;
	}

	bool operator<(const Object& Ob)const {

		return z < Ob.z;
	}
};

int main()
{
	priority_queue <Object>pq;
	pq.push(Object(1, 2, 3));
	pq.push(Object(4, 1, 2));
	pq.push(Object(3, 2, 1));
	pq.push(Object(-1, 2, 7));

	while (!pq.empty())
	{
		printf("%d %d %d\n", pq.top().x, pq.top().y, pq.top().z);
		pq.pop();
	}
}

---

x,y,z라는 위치 값을 갖고 있는 Object라는 구조체가 있을 때,

이것을 priority_queue에 넣고 z값에 따라 정렬하고 싶으면

구조체 안에

	bool operator<(const Object& Ob)const { //const를 안써주면 에러 발생

		return z < Ob.z;
	}

 

라는 코드를 삽입해줘야 한다.(const를 위치에 맞게 넣어주지 않으면 에러가 발생)

이것이 바로 operator overloading(연산자 오버로딩)이다. 

정확히 말하면 비교연산자 오버로딩인데

 

우리가 흔히 쓰고있는 연산자들 (-,+,%,/ ,>, < ,== 등등)이 있는데 '<'연산자를 보자.

보통 우리가 코드내 선언 할 때 'a < b' 이렇게들 사용한다.

하지만 이 코드가 a.operator<(b)로 변환되어 내부에서 작동한다.

 

a=1, b=2라면, a.operator<(b) 는 true값을 반환한다.

그렇기에 return a<b는 사실 a.operator<(b)의 반환값인 것.

 

 

다시 priority_queue를 보자.

 

priority_queue는 a와 b를 비교해서 큰 값을 위로 올려주는 heap을 만들어주는 queue이다.

 

그러므로 max_heap의 특성에 따라

a<b일 때, b가 크다면 b를 위로 올려주고, a가 크다면 a를 위로 올려주는 것. 

=

즉, a.operator<(b)의 반환값이 1(참)이면 b를 올려주고, a.operator<(b)의 반환값이 0(거짓)이면 a를 올려준다.

 

[간단하게 말하면, 참이면 나중에 온 애를 위로 올린다]

 

그런데 내부 멤버변수가 여러개인 struct를 priority_queue에 넣어준다면

우리가 이 operator를 정의해줘야 하는데 이것이 overloading이다.

 

	bool operator<(const Object& Ob)const {

		return z < Ob.z;
	}

이 코드를 다시 보면,

heap에 어떤 값이 이미 있을 것이다. 그 값이 연산자 왼쪽에 있는 애,

그리고 어떤 값이 새로 들어올 것이고 이는 연산자 오른쪽에 있는 애,(여기선 Object Ob)

 

위 코드를 통해 priority_queue를 만든다고 할 때,

 

 

만약, x,y,z의 멤버 변수를 가진 Object라는 struct가 있다고 하자.

struct Object {
	int x;
	int y;
	int z;

	Object(int a, int b,int c)
	{
		x = a;
		y = b;
		z = c;
	}
}

 

(1,2,3)의 멤버변수를 가진 Object가 새로 heap에 들어왔다.

priority_queue <Object>pq;
pq.push(Object(1,2,3));

아무 값도 없으니 당연히 맨 위에 위치

 

 

다음으로 (4,1,2)의 값을 가진 Object가 새로 heap에 들어왔다.

 

pq.push(Object(4,1,2));

 

	bool operator<(const Object& Ob)const {

		return z < Ob.z;
	}

위에 쓴 새로 정의된 '<'연산자를 통해서

 

원래있던Object.operator<(나중들어온Object) 가 수행되고

 

그 overloading의 내용인

  '원래있던Object의z값 < 나중들어온Object의z값' 비교를 수행한다.

 

우리의 예시에선,

(1,2,3)의 z값 < (4,1,2)의 z값 ===> 3 < 2이므로 거짓을 출력하게 되고

(이는 즉, 원래 있던 애 < 새로 온 애)

 

비교를 마치고 새로들어온 (4,1,2)는 heap의 아래로 내려주게 된다.

 

(원래)3<(나중)2 이므로 나중에 들어온애를 내려줌 

 

반복해서

(3,2,1)과 (-1,2,7)을 순서대로 push해 준다면

	pq.push(Object(3, 2, 1));
	pq.push(Object(-1, 2, 7));

 

다음과 같이 z값으로만 max_heap을 생성한 priority_queue를 볼 수 있다.

 

이걸 위에서부터 빼주고 출력해본다면

	while (!pq.empty())
	{
		printf("%d %d %d\n", pq.top().x, pq.top().y, pq.top().z);
		pq.pop();
	}

 

 

 

z의 값에 따른 순서대로 나온다.

 

 

---

사실 코딩테스트에서는 조금 더 복잡한 방식으로 pQ를 형성해야 할 때가 있다.

이를 심화해서

 

조건이

 dis가 가까운 Object를 heap 의 top에

 만약 dis값이 같다면,

 y값이 더 작은 Object를 heap 의 top에

  만약, y값도 같다면

   x값이 더 작은 Object를 heap top에 올리는 조건

이라면,

 

	bool operator<(const Object& bb)const {
		if (dis == bb.dis) { //dis가 같다면
			if (y == bb.y)//그런데 y도 같다면
			{
				return x > bb.x; //나중 들어온 애가 x가 작을 때 올려줌
			}
			else return y > bb.y;; //y는 다르다면
			//나중 들어온 애가 y가 작은 게 참일 때 올려줌
		}
		else return dis > bb.dis; //dis가 다르다면
		//나중 들어온 애가 dis가 작을 때 올려줌
	}
};

이다.

헷갈리지만...

 

[priority_queue는 a.operator<(b) 가 참일 때 b를 heap의 top에 올려준다]

 

만 기억하면 될 것 같다.