[c++ / STL] sort, priority queue
1. sort
헤더파일 : <algorithm>
sort(start,end)를 이용하여 [start,end)의 범위에 있는 요소를 오름차순(default)으로 정렬해주는 함수이다.
퀵 정렬을 기반으로 합수가 구현되어 있고, 평균 시간 복잡도는 O(nlogn)이다.
-
sort(arr, arr+n); //배열
-
sort(v.begin(), v.end()); //벡터
-
sort(v.begin(), v.end(), compare); //사용자 정의 함수 사용
-
sort(v.begin(), v.end(), greater<자료형>()); //내림차순 (Descending order)
-
sort(v.begin(), v.end(), less<자료형>()); //오름차순 (default = Ascending order)
출처: https://blockdmask.tistory.com/178 [개발자 지망생]
2. Priority_Queue
헤더파일 : <queue>
선언 : priority_queue<자료형,container,비교함수> 변수명
->선언한 자료형 변수들을 비교함수에 따라 정렬
priority_queue<int,vector<int>,cmp> pq;
복사 :
priority_queue<int,vector<int>,cmp> pq(vec.begin(),vec.end());
추가 및 삭제 :
push(element) ->비교함수에 따라 내부적으로 정렬됨
pop() ->맨 앞 원소 삭제
반환:
top() ->맨 앞에 있는 원소를 반환
기타:
empty()
size()
구현
내림차순(default)
int main(){
// priority_queue
priority_queue< int, vector<int>, less<int> > pq;
// push(element)
pq.push(5);
pq.push(2);
pq.push(8);
pq.push(9);
pq.push(1);
pq.push(14);
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
출력 : 14 9 8 5 2 1
오름차순
int main(){
// priority_queue
priority_queue< int, vector<int>, greater<int> > pq;
// push(element)
pq.push(5);
pq.push(2);
pq.push(8);
pq.push(9);
pq.push(1);
pq.push(14);
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
출력 : 1 2 5 8 9 14