C++에서 힙을 적용해보자!
사용법
생성
#include <queue>
priority_queue<int, vector<int>, greater<int>> pq;< >안에 들어있는 정보들!
int(어떤 타입의 데이터를 저장할 것인가?)vector<int>이 힙을 저장하기 위해서 어떤 컨테이너를 사용할 것인가?greater<int>대소비교할 때 사용, 지정하지 않으면 less가 지정된다.
-> less가 지정되면 Max heap이 된다.
-> greater을 쓰면 Min heap으로 작은 것부터 나온다.
int 뿐만 아니라 pair, 구조체 등등 모든 타입이 가능하다!
비교 연산자 직접 만들기
less, greater뿐만 아니라 직접 만들어서 사용할 수 있다.
struct S{
int left;
int right;
};
struct cmp{
bool operator()(S n1, S n2){
return n1.left < n2.left;
// 지금은 큰 것부터 나오게 된다.
// 작은 것부터 나오게 하려면 ">"로 바꾸면 된다!
}
};
priority_queue<S, vector<S>, cmp> pq;밑에는 사용 예시이다.
#include<iostream>
#include<queue>
using namespace std;
struct S{
int left;
int right;
};
struct cmp{
bool operator()(S n1, S n2){
return n1.left < n2.left;
}
};
int main(){
priority_queue<S, vector<S>, cmp> pq;
pq.push({1,0});
pq.push({5,2});
pq.push({3,7});
pq.push({6,5});
pq.push({7,2});
while(!pq.empty()){
S tmp = pq.top();
pq.pop();
cout << tmp.left << " " << tmp.right << endl;
}
return 0;
}
// left들이 큰 것부터 나온 것을 볼 수 있다.
7 2
6 5
5 2
3 7
1 0원소 추가 및 삭제
pq.push(element); -> 원소 삽입
pq.pop(); -> 큐에서 top에 있는 원소 삭제원소 반환
pq.top(); -> 가장 우선순위가 높은, top에 위치한 원소를 반환해준다기타
pq.empty(); -> 큐가 비어있다면 true, 그렇지 않다면 false 반환
pq.size(); -> 큐에 들어있는 원소들의 개수 반환참고자료
옹골찬 개발자가 되기 위한 험난한 일대기