[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