내림차순, 오름차순

pq : 240109

디폴트는 less<>이고, 큰값이 top 에 위치함.

• 만약에 낮은 값이 top 위치에 오게 만들고 싶다면!
  priority_queue<int, vector, greater> pq;
  이런식으로 작성해야 함.

시퀀스 컨테이너와의 차이

• pq는 힙 구조로 되어 있어서 높은값이 top에 위치함.
  

---

1. 선언 및 사용

기본 선언 과 사용

• 디폴트값은 내림차순이다.

: 매개변수 하나만을 사용한다. 이때 출력하면 내림차순으로 나온다.

사용하기

잘못된 사용방법 - 1번

-> 우선순위 큐는 begin과 end 이터레이터를 지원하지 않으므로 Ranged for문 사용불가능하다.

잘못된 사용방법 - 2번

• size로 접근하기
  
  -> -71과 1이 나오지 않는 것을 확인할 수 있다.
  왜냐하면 반복문을 진행할때마다 pop에 의해 size가 줄어들기 때문이다.

  즉 우선순위큐는 size로 접근하면 안된다.
  우선순위큐의 empty하는 함수를 통해 접근하자!

올바른 사용방법

• empty함수로 접근하기
  
  -> 내림차순으로 출력되는 것을 확인할 수 있다.

비교함수를 이용하기 위한 선언

• 오름차순으로 변경해보자.

-> 기본 형식으로는 불가능하다.

• 이런식으로 선언해야 오름차순이 가능하다.
  

따라서 우선순위 큐 선언자체를 이런 방식으로 사용하도록 하자.
priority_queue<int, vector, greater>pq;

• 내림 차순 예제
  

https://kibbomi.tistory.com/149

sort할때 와 비교방식에 차이가 있따.

: sort할때 greater로 하면 내림차순이 나오지만, 우선순위큐는 greater는
오름차순이다.

어떻게 이해하냐면 컨테이너를 sort할때는 맨앞에 있는 친구가 비교구문에 따라야 한다.
우선순위큐는 비교함수를 그대로 따른다고 생각하자.

2. 컨테이너값 복사로 초기화하기

-> 뒤에다가 이터레이터 방식을 이용하면 선언과 동시에 초기화가 가능하다.

3. 우선순위큐에서의 정렬

• 뒤쪽이 더 크므로 오름차순이다.

• 기존 sort로 정렬할때는 비교함수를 포인터 값을 3번째 인자값에 넣어주었다.
  

  but, 우선순위큐는 구조체 또는 클래스를 작성해서,
  비교 연산자를 이용해야 한다.

  

  혼동할 수 있는점.

  우선순위큐는 top()을 기준으로 해서 정렬이 이루어진다.
  top()이 매개변수 첫번째 값이라고 생각하자.
  sort()와 비교하면 출력되는 값이 반대로 나와서 의아해 할 수 있다.

  c++ reference 참고

  
  -> greater일때 가장 작은요소가 top()으로 들어온다.

4. pair값을 이용한 정렬

• 디폴트 pair 정렬
  : first랑 second 각각 높은 값이 위로 위치하는 것을 확인할 수 있음.
  
• first값은 정렬되었지만, second값은 규칙없이 정렬된 것을 확인할 수 있다.
  
• first값은 오름차순으로 하고, second값은 내림차순으로 정렬해보자.