혼자서 공부하는 블로그

헤더를 추가할 것! 이 포스트에서 다루는 함수들은 정확히는 vector의 원소들을 힙의 형태를 띄도록 재배치한다. 따라서 vector 관련 함수가 함께 쓰여야 한다. make_heap() 시간복잡도: O(n)으로 구현되어 있다. 사용법: 1) make_heap(v.begin(), v.end()); v라는 vector의 원소들끼리 서로 순서를 바꾸어 max heap이 되도록 한다. 2) make_heap(v.being(), v.end(), cmp); 그런데 max heap이 아니라 min heap을 만들고 싶다면? sort함수처럼 위와 같이 비교함수(cmp)를 작성해서 인자로 넣으면 된다. 코드 예시: bool cmp(int a, int b) { if (a > b) return true; else retu..

C++의 sort() 함수는 직접 비교함수를 작성해서 정렬할 수 있다. 비교함수는 두 개의 파라미터를 가지며(비교하려는 원소 a와 b) bool값을 반환하도록 작성해야 한다. 이때, 두 원소의 순서가 올바르면 true, 아니면 false를 반환토록 한다. 예를 들어 오름차순 정렬을 하고 싶다면 a < b이면 true, else는 false를 반환하면 된다. 비교함수는 Strict Weak Ordering을 준수해야 한다. 이를 준수하지 않고 프로그램을 작성하면 비주얼 스튜디오에서는 "Expression: invalid comparator"라는 에러를 맞닥뜨릴 것이다. Strict Weak Ordering은 다음의 네 가지 조건을 만족해야 한다. 1) irreflexivity(비반사성) - 모든 x에 대해..