[STL] Priority Queue(1) - heap, sort, compair 설정

2025.03.09

 

1. Priority Queue

* stack : 나중에 들어온 데이터가 먼저 나감 LIFO

* queue : 먼저 들어온 데이터가 먼저 나감 FIFO

*priority_queue: 우선순위 높은 데이터가 먼저 나감

 

구현???

sequence	push O(1)	pop O(n)  우선순위 찾아야해서
heap (주로 이거 사용)	push O(log n)	pop O(log n)

​

2. Heap

두가지 특성을 만족함

1) 완전 이진트리	2) 부모 노드의 우선순위가 자식 노드의 우선순위보다 높다
-  모든 노드의 자식 노드는 최대 2개   - 노드는 위에서부터, 왼쪽부터 꽉 채워진다	ex) 값이 클수록 우선순위가 높다 : MAX_HEAP

    => 최우선순위 노드는 루트에 존재!

 

2-1. Heap : 구성

표현은 트리 형태로 하지만 실제 저장은 단순 배열만으로 가능하다 (단순히 부모자식 정도라서)

완전 이진트리이기 때문에 각 노드의 부모, 자식의 인덱스를 수식으로 구할 수 있다.

 

시작점이 0이나 1이냐에 따라 달라질 수 있음.

 

2-2. Heap : push

1) 마지막 위치에 추가 (완전 이진트리 만족)

2) 추가한 노드를 부모노드랑 비교하며 우선순위 높으면 바꿔 올라간다

 

          => 실행 과정이 이렇게 되니까 시간복잡도는 트리의 높이만큼인  O(log N) 이 된다

 

2-3. Heap : pop

: 무조건 맨 위를 제거해야함. + 완전 이진트리를 만족시키기 위해 맨 위에꺼를 swap 후 pop함

1) 루트와 마지막 노드를 바꾸고 haep size를 감소시킨다

2) 루트 노드에서부터 우선순위 높은 자식노드와 비교하여 우선순위가 낮으면 바꿔내려간다

 

이렇게 삭제를 하고 나면 heap의 조건 중 하나인

" 부모 노드의 우선순위가 자식 노드의 우선순위보다 높다 "

가 성립하지 않기 때문에 swap 해서 heap을 정리해줘야한다.

          => 실행 과정이 이렇게 되니까 시간복잡도는 트리의 높이만큼인  O(log N) 이 된다

 

2-4. Heap : sort

: MAX_HEAP : 오름차순 (큰 값이 뒤에 쌓인다)

: MIN_HEAL : 내림차순 (작은 값이 뒤에 쌓인다)

둘다 시간복잡도 N log N

 

1) n개의 data를 heap에 push

2) n번 pop진행 (pop할 때 루트와 마지막 값 swap)

     : 최우선순위 값이 순차적으로 뒤쪽부터 쌓인다

3. STL Priority_queue

#include <queue>

heap으로만 구성

default : vector<T>, less <T>

top만 접근 가능

template<
       class T,
       class Container = std::deque<T>
       class Compare = std:less<typename Container::value_type>
> class priority_queue;

*** less == max_heap

보통 l < r 이면 l이 우선순위라서 헷갈릴 수 있는데 priority_queue는 r 이 top에 와야함! 

<<<<<이런 느낌으로 제일 작은게 제일 앞에!

 

priority_queue<T> pq
priority_queue<T, vector<t>, Compare> pq
// greator : min pq,  less : max pq

pq = {} // clear

void pq.push(x)
void pq.pop()
T    pq.top()
int  pq.size()
bool pq.empty()

4. Compare 설정 -  int ver

#Function Object 으로 설정

1) pre- defined function object

• less<T> : 큰 값이 top (key type에  operator < 정의 필수)
• 값이 클수록 우선순위 높음

template<class T>
struct less{
	bool operator()(const T& l, const T& r)const{ // 참조자&는 권장 const는 필수
    	return l<r; //이거 중요함!!! pq는 비교 반대로!!!
    }
};

priority_queue<int> maxpq;
priority_queue<int, vector<int>, less<int>> maxpq;

 

• greater<T> : 작은 값이 top (key type에  operator > 정의 필수)
• 값이 작을수록 우선순위 높음

template<class T>
struct greater{
	bool operator()(const T& l, const T& r)const{
    	return l>r; //이거 중요함!!! pq는 비교 반대로!!!
    }
};

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

 

2) user- defined function object

• int 절대값 오름차순: 절대값이 큰 값이 top 
• 절대값이 클수록 우선순위 높음

struct AbsComp{
	bool operator()(const T& l, const T& r)const{
    	return abs(l) < abs(r); // pq는 비교 반대로!!!
    }
};

priority_queue<int, vector<int>, AbsComp<int>> abspq;

 

4. Compare 설정 -  custom data ver

#Function Object 으로 설정

1)  default less<T> 활용 (operator < 정의 필수)

• 값이 클수록 우선순위 높음, a값이 큰게 top

template<class T>

struct Data{
	int a, b, c;
	bool operator<()(const T& r)const{ // 참조자&는 권장 const는 필수, 설정한 operator만 사용가능
    	return a < r.a;
        //형태가 같아야함. a<b (errer)  a < r.a (O)  b < r.b (O)   a+b < r.a+r.b (O)
    }
};

priority_queue<int> maxpq;
priority_queue<int, vector<int>, less<int>> maxpq;

 

2) user- defined function object

struct Data{ int a, b, c;};
	
struct Comp{
	bool operator()(const T& l, const T& r)const{
    	return l.a < r.a; 
    }
}

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

 

++++++++++++++++++++++++++++++++++++