c++/ 자료구조&알고리즘 개념 복습하기 - 15 / 우선순위 큐, STL priority_queue, 절대값

한창희·2022년 4월 29일

c++ 정리

c++ 자료구조/알고리즘 개념 복습

목록 보기

15/23

< 우선순위 큐 >

pop을 하는 경우, 가장 먼저 들어온 원소가 나오는 대신, 우선순위가 가장 높은 원소가 나오는 큐!
힙 구조 활용!!!

원소의 추가 = O(logN)
우선순위가 가장 높은 원소의 확인 = O(1)
우선순위가 가장 높은 원소의 제거 = O(logN)

< 힙 >

이진 트리 기반
최대값, 최소값을 찾을때 유용
높이 같은 경우 왼쪽부터 채워나간다
최소힙 = 부모가 자식보다 작아야한다, 작아야 우선순위 높다
-> 루트가 가장 작음
최대힙은 최소힙과 반대!

< STL priority_queue >

STL에서는 기본적으로 최대힙!!
greater를 통해 최소힙으로 가능
priority_queue가 set보다 속도 빠름

priority_queue<int, vector<int>, greater<int>> pq;

-> 최소힙!!

< priority_queue 비교 함수 구현법 >

#include<iostream>
#include<queue>
#include<cmath>

using namespace std;

struct cmp {
	bool operator()(int first, int second) {
		if (abs(first) > abs(second)) return true;   // 절대값이 작은 것에 우선순위를 높게 주겠다!! -> 일반 sort와 반대로 생각!!
		else if (abs(first) == abs(second)) {
			if (first > second) return true; // 절대값이 같다면 원래 값이 더 작은 것에 우선순위 높게 주겠다
			else return false;
		}
		else return false;
	}
};

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	priority_queue<int, vector<int>, cmp> pq;

	pq.push(1);
	pq.push(-1);
	pq.push(-5);
	pq.push(5);
	pq.push(8);
	pq.push(-12);

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

	return 0;
}