#include index로 임의 접근이 가능한 자료구조라면 STL heap 관련 함수 적용 가능 : arr, vector 1. make_heap(배열.begin(), 배열.end() , 생략가능 less) : O(N), max 3N (???) 새로운 자료구조로 생성되는게 아니라, 기존 배열을 힙 정렬 형태로 재배열하는 형태로 힙을 구성한다. 기본 max heap으로 정렬된다. greater functor로 min heap 정렬도 가능하다. 2. pop_heap(배열.begin(), 배열.end()) : O(logN), max logN 재배열 후 [0] 이 head가 된다. pop_head는 head를 맨 마지막 인덱스와 뒤바꾸고, 맨 마지막 인덱스 전까지를 다시 heap 형태 재정렬해준다. vect..
#include priority_queue : less or greater 맨 뒤부터 반환한다. less 면 오름차순 정렬이니까 제일 큰것부터 반환됨, greater는 내림차순 정렬이니까 제일 작은것 부터 반환될것. 내가 정렬 함수를 순위 높은걸 앞으로 가게 만들었을 때 priority_queue 는 순위 낮은걸 먼저 뱉게된다. push, pop, top 등 사용가능
1. map key, value로 이루어진 컨테이너 key값을 기준으로 자동 정렬 (기본 오름차순 정렬, 내림차순도 정의 가능) ***레드블랙 트리로 구현되어 있다고 한다.. 레드블랙트리가 뭐지? https://hyo-ue4study.tistory.com/149 1. #include 2. 선언 : map 변수명 3. 검색 : m.find(key) -> 존재하면 해당 이터레이터 반환. 없으면 m.end() 반환 4. 삽입 : m.insert(make_pair( , ) or { , }) -> 중복 허용x. key가 중복되면 insert 수행 안됨 5. 접근 : 랜덤 접근 불가. begin() 부터 서치해야함. next, prev 함수 사용 가능 ***for (auto m : map) 으로 접근하면 직..
prev, next, advance prev 와 next 의 경우 n = 1은 생략 가능 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dkdldhekznal&logNo=221319370996
벡터나 배열, 데크 등 인덱스 접근이 가능한 자료구조의 경우 오름차순 정렬을 한 후, lower_bound(begin,end,타겟) 으로 사용. set이나 map 등 자체적 순서를 가지는 (ex. 이진트리) 자료구조 형태를 띄는 경우 S.lower_bound(타겟) 으로 사용한다.
