본 문서에서는 C++에서 사용하는 표준 라이브러리 중 자주 사용되는 알고리즘에 해당하는 내용을 다룬다.
최종수정일 : 2023.06.14
` #include <algorithm> template <class RandomAccessIterator> void sort(RandomAccessIterator first, >RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); `
standard : C++11
` #include <regex> typedef basic_regex<char> regex; `
,
` #include <algorithm> make_heap(RandomAccessIterator first, RandomAccessIterator last, [Compare cmp]); push_heap(RandomAccessIterator first, RandomAccessIterator last, [Compare cmp]) pop_heap(RandomAccessIterator first, RandomAccessIterator last, [Compare cmp]) sort_heap(RandomAccessIterator first, RandomAccessIterator last, [Compare cmp]) priority_queue `
make_heap
컨테이너의 [first,last) 영역을 힙으로 만든다. cmp가 greater<>() 또는 내림차순( p1true - if(param1 > param2) return true; )인 경우, 자식 노드가 부모 노드보다 크고, less<>() 또는 오름차순인 경우 자식 노드가 부모 노드보다 작다.
pop_heap
힙 구조에서 가장 상위에 있는 노드를 컨테이너의 마지막 위치로 보낸다. [first, last-1) 영역의 컨테이너는 힙의 속성을 유지한다. 제거되어 대체되는 노드의 속성은 cmp에 따른다.
push_heap
[first, last-1)의 영역에서 힙의 속성을 가지고 있는 컨테이너에 대해서 [first, last)의 영역까지 힙의 속성을 갖도록 영역을 확장한다. 삽입되는 노드의 속성은 cmp에 따른다.
sort_heap
힙 구조의 컨테이너를 다시 정렬한다. 정렬 대상인 힙이 cmp로 생성되는 힙의 형식과 일치하여야 하며, cmp에 따라 정렬된다. 원할 경우 reverse()와 함께 사용될 수 있으며 sort()
에 비해 특별히 나은 점이 있지는 않은 것으로 확인된다.
priority_queue
자료구조 priority_queue는 자동으로 위 함수들을 호출하여 힙 구조를 유지한다.