[Algorithm] priority_queue

1. priority_queue : 완전이진트리 (complete binary tree)

2. heapify :  직접 연결되어 있는 노드끼리 비교해서,

  - max heap 기준 : 큰 값을 위로 올린다.

  - min heap 기준 : 작은 값을 위로 올린다.

 

- Ex. heapify

push(15) 시 heapity 발생

 

 

7 - 9 heapify

디버깅 모드로 swap 완료 확인

 

 

3. priority_queue 와 algorithm의 sort 정렬 차이

똑같이 less 정렬 시, heapq(priority_queue)는 내림차순으로 정렬되고, sort 정렬 시, vector가 오름차순으로 정렬됨을 볼 수 있다.

 

priority_queue는 less<> 와 같이 사용하고, sort는 less<>() 와 같이 사용한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct data {

	bool operator()(int a, int b) {
		return a < b;
	}
};

bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	
	priority_queue<int, vector<int>, struct data> pq;
	pq.push(5);
	pq.push(15);
	pq.push(7);
	pq.push(3);
	pq.push(2);
	pq.push(9);
	pq.push(10);

	vector<int> v;
	v.push_back(5);
	v.push_back(15);
	v.push_back(7);
	v.push_back(3);
	v.push_back(2);
	v.push_back(9);
	v.push_back(10);
	sort(v.begin(), v.end(), cmp);
}

priority_queue는 cmp를 구조체나 클래스 안에 operator()를 만들어 사용하고, sort는 함수로 선언하여 사용한다. 

 

 

차이점

1. sort에서는 less가 오름차순, priority_queue에서는 less가 내림차순

2. sort에서는 less<>() 과 같이 사용, priority_queue에서는 less<>와 같이 사용

3. sort에서는 cmp를 함수로 선언하여 사용, priority_queue는 구조체나 클래스 안에 operator() 에 구현하여 사용