vector, priority_queue 정렬 비교

우선순위 큐에 template 타입을 자료형만 주게 되면 기본은 max heap 이다.

벡터의 경우 sort 호출 시 기본은 오름차순이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main() {
	vector<int> v;
	priority_queue<int> pq;

	v.push_back(10);
	v.push_back(5);
	v.push_back(20);
	sort(v.begin(), v.end());

	pq.push(10);
	pq.push(5);
	pq.push(20);

	cout << "vector(sort): ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}

	cout << "\npriority_queue: ";
	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
}

콘솔 실행 결과

sort 함수는 비교 용도의 함수와 operator 선언 된 class, struct를 매개변수로 받을 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct cmp {
	bool operator()(int a, int b) {
		return a > b;	// vector = 내림차순 (false swap), queue = min_heap (true swap)
	}
};

bool compare(int a, int b) {
	return a < b;	// vector = 오름차순, queue = max_heap
}

int main() {
	vector<int> v;
	priority_queue<int, vector<int>, cmp > pq;	// min_heap
	priority_queue<int, vector<int>, bool (*)(int, int) > pq2(compare);	// max_heap

	v.push_back(10);
	v.push_back(5);
	v.push_back(20);
	sort(v.begin(), v.end(), cmp());	// 내림차순 정렬
	sort(v.begin(), v.end(), compare);	// 오름차순 정렬

	pq.push(10);
	pq.push(5);
	pq.push(20);

	pq2.push(10);
	pq2.push(5);
	pq2.push(20);

	cout << "vector(sort): ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}

	cout << "\npriority_queue1(min): ";
	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}

	cout << "\npriority_queue2(max): ";
	while (!pq2.empty()) {
		cout << pq2.top() << " ";
		pq2.pop();
	}
}

콘솔 실행 결과

sort 함수는 아래와 같이 오버로드 되어있다.

 

sort 오버로드

---

벡터를 sort 함수로 정렬할 때와 우선순위 큐의 compare 정렬은 반대이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main() {
	vector<int> v;
	priority_queue<int, vector<int>, greater<int> > pq;

	v.push_back(10);
	v.push_back(5);
	v.push_back(20);
	sort(v.begin(), v.end(), greater<int>());

	pq.push(10);
	pq.push(5);
	pq.push(20);

	cout << "vector(greater sort): " << v.front() << "\n";
	cout << "priority_queue(greater sort): " << pq.top() << "\n";
}

 

콘솔 실행 결과

위의 실행 결과와 같다.

이유는 벡터 정렬은 직관적으로 앞, 뒤 요소를 비교하고 조건이 참이 아닐경우(false) swap하게 된다.

반대로 우선순위 큐는 parent와 child를 비교하여 greater의 경우 parent > child를 리턴하고,

조건이 참일 경우(true) swap한다. child가 parent와 교환 되므로 top 실행 시 적은 요소가 top에 있게 된다.

---

Custom compare

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>

using namespace std;

class Data {
public:
	int num;
	string id;

	Data() {}
	Data(int num, string id) {
		this->num = num;
		this->id = id;
	}

	bool operator()(const Data a, const Data b) {
		if (a.num == b.num) {	// num 이 같을 경우
			return a.id > b.id;	// id 비교
		}
		else return a.num > b.num;	// min_heap
	}
};

bool cmp(Data a, Data b) {
	if (a.num == b.num) {
		return a.id > b.id;
	}
	else return a.num > b.num;
}

int main() {
	priority_queue<Data, vector<Data>, Data> q;
    //priority_queue<Data, vector<Data>, bool (*)(Data, Data)> q(cmp);	// 가능

	q.push(Data(10, "AA"));
	q.push(Data(50, "BB"));
	q.push(Data(30, "CC"));
	q.push(Data(5, "DD"));
	q.push(Data(70, "EE"));

	cout << q.top().num << " " << q.top().id << "\n";
}