-
c++ standard Library 책
:11.9 절 참고.. -
우선순위큐는 일반적인 sort에서 비교연산자를 처리한 것과는 다르게
정렬이 된다.
- 참고 사이트
https://hagisilecoding.tistory.com/60
그리고 프로그래머스의 힙 강의
priority_queue에서의 push 정렬에 대해서! 240518
- 이유 less 로 설정하고 진행하자.
- 10 을 넣으면 아무것도 없기 때문에 root node에 놓여짐.
- 5를 넣으면 기존의 10은 왼쪽에 위치하고, 5는 오른쪽에 위치하는 형태가 된다. - 이어서 10 vs 5 의 비교를 하게 되고 vs 에 less 이기 때문에
10 < 5 ??? 의 비교식이 형성된다. 여기서 알아야 할 부분은 true가 되면 swap이 일어나고,, false면 그대로다. - 그 결과 아직까지 루트노드는 10이고, 10의 자식leftNode에 5가 위치함.
- 15가 push 하게 되면, 현재 트리 구조는 rightNode가 없고, 완전 이진트리구조를 만들어야 하기 때문에 10의 rightNode에 오고, 비교를 한다.
- 10 < 15 ?? true이기 때문에 swap이 일어나고, 루트노드는 15로 변경된다.
-> 이러한 완전이진트리 구조에서 비교 연산을 함으로써, sort에서의 정렬 결과와는 다르게 priority_queue는 내림차순으로 만들어지는 것을 확인할 수 있다.
우선순위큐에서 push 정렬에 대해서 새롭게 push되는 값은 트리의 마지막 노드에 들어오고, 그 상태에서 부모 노드와 비교를 한다.
less 인 경우, 부모 < 새롭게 들어온값
greater인 경우 , 부모 > 새롭게 들어온 값.
이고, true인 경우, 부모와 자식 노드를 swap하고, 계속 재귀적인 형태로 진행됨
false 인 경우, swap일어나지 않는다.
sort vs pq : 240518
: h파일을 쫓아가면 디폴트값이 less( < ) 을 확인할 수 있다.
-
하지만 출력해보면, sort의 경우, 예상할 수 있게 오름차순 정렬이 되었고,
priority_queue의 경우는 이와 반대로 내림차순 정렬이 되었다.
-
결론
: sort의 디폴트는 오름차순이고, pq의 디폴트는 내림차순이라는 것을 기억하자. -
아마 이유는 힙 알고리즘에 의해서 인것 같은데, 공부 필요
함수 객체에서 알아야할점
-
참고 자료: 뇌를 자극하는 stl 페이지 82
less 객체는 < 연산자의 함수 객체이다.
greater 객체는 > 연산자의 함수 객체이다.
즉 기준은 2개의 인자의 경우( const int & a , const int &b) 에서
앞의 a를 기준으로 해서 진행된다. -
개인적인 생각으로는 뒤로갈수록 커져야 하는게 아닐까 싶었지만,
c++에서 제공하는 greater의 연산자는 > 오른쪽으로 향해 있기 때문에,
앞의 값이 뒤의 값보다 더 크다.
예제
sort함수에서
: 위의 함수객체를 그대로 따른다.
1. greater : 내림차순
: 아래 실행결과를 보면, greater는 > 이기 때문에 내림차순으로
정렬된다.
2. less : 오름차순
: less 함수 객체는 < 이기 때문에 오름차순으로 정렬된다.
3. compare 함수 사용
앞선 값 a를 기준으로 해서 정렬된다.
sort 함수의 비교함수를 그냥 전역함수로 만들어 주면 된다.
-
a가 기준이므로 a와 다음 값 b 비교 하는 것이므로
뒤로 갈수로 값이 작아지는 내림차순의 결과를 확인할 수 있다.
-
뒤로 갈수록 값이 커진다.
우선순위 큐와 일반 타입.
: cpp reference를 확인하면 greater 일때는 가장 작은 값이 top()으로 향하게 되므로, greater가 오름차순이다.
- 디폴트값.
가장 낮은 값이 top()에 위치함.
이렇게 사용하자.
- 정형화 시키자.
priority_queue<int, vector , 비교 함수 작성 > pq;
1. greater : 순차열에서는 내림차순인데, pq에서는 오름차순이다.
2. less : 내림차순
3. compare 함수 사용
우선순위큐의 비교함수를 struct의 operator 연산자를 이용해 만들어야 한다.
: b가 top이라고 생각하고 접근하자.
우선순위 큐와 pair 타입.
내림 차순
오른 차순
비교 대상의 기준
: 내림차순과 오름차순을 확인을 해보면, first 값을 기준으로 하고 있음.
비교 대상을 second로 할 수 는 없을까?
: 가능함.
