| 이번에 STL에 대한 공부를 하며 작성하기로 했다. 모든 STL에 대한 내용은 CppCon 2018: Jonathan Boccara “105 STL Algorithms in Less Than an Hour”를 참조했다. ( 링크 : https://www.youtube.com/watch?v=2olsGf6JIkU&t=964s )오늘은 STL의 make_heap, sort_heap, push_heap 등 heap 관련 연산을 작성하겠다. 그전에 힙과, 힙정렬에 대해 간단히 알아두면 좋다. 링크 : https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) ( 힙에 대한 위키피디아의 정보 ) |
<make_heap>
make_heap 은 [first, end) 구역에 있는 모든 원소를 힙으로 만들어 냅니다.
인자로는 first, end, functor = less<> 를 받습니다. make_heap 은 기본적으로 최대 힙( max heap ) 을 구성합니다.
| 1 2 3 4 5 6 |
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; std::make_heap(arr, arr + 10); // 최대 힙 std::make_heap(arr, arr + 10, [](int _t1, int _t2) ->bool { return (_t1 < _t2); }); // 최대 힙, 람다도 사용 가능 std::make_heap(arr, arr + 10, greater<int>()); // 최소 힙, greater나 less 도 사용가능 |
임의 접근 반복자가 있다면, 모든 컨테이너에 대해서 heap을 만들어 낼 수 있습니다.
| 1 2 3 4 5 6 7 |
vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; array<int, 10> narr = { 1,2,3,4,5,6,7,8,9,10 }; list<int> nlist = { 1,2,3,4,5,6,7,8,9,0 }; std::make_heap(nvt.begin(), nvt.end()); //ok , vector는 임의 접근 반복자 입니다 std::make_heap(narr.begin(), narr.end()); //ok, array 도 임의 접근 반복자 입니다. std::make_heap(nlist.begin(), nlist.end()); // error, list는 양방향 반복자 입니다. |
make_heap은 log(N)의 복잡도를 가지며 최대 3N 까지 비교합니다.
<push_heap>
push_heap은 이미 만들어진 힙 컨테이너에 힙을 다시 추가하는 함수입니다.
| 1 2 3 4 |
vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; make_heap(nvt.begin(), nvt.end()); nvt.push_back(100); push_heap(nvt.begin(), nvt.end()); // 최대 힙은 100 |
이게 왜 이렇게 작동하냐에 의문점이 들 수도 있습니다.
예로부터 힙을 생성하고, 새로운 값을 넣을땐 end 번째의 노드에 새로운 값을 추가하고, 그것을 부모노드와 비교하며 재 정렬 해주었습니다.
위 또한 100의 값을 마지막에 넣고, push_heap으로 맨 마지막 노드인 100을 재 정렬 해나가는 과정이라고 보시면 됩니다.
push_heap은 O(log N)의 복잡도를 가지며, 최대 log N 번의 비교를 수행합니다.
<pop_heap>
pop_heap은 만들어진 힙 컨테이너에 루트노드를 빼내는 함수입니다.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int main() { vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; std::make_heap(nvt.begin(), nvt.end()); for (auto& i : nvt) { cout << i << endl; }// 10 9 7 8 5 6 3 1 4 2 std::pop_heap(nvt.begin(), nvt.end()); for (auto& i : nvt) { cout << i << endl; } // 9 8 7 4 5 6 3 2 1 2 10 int i = nvt.back(); // 힙의 최댓값(10) 을 가져옵니다. nvt.pop_back(); // 최댓값을 삭제합니다. } |
위 같은 경우, nvt는 max heap 으로 설정되었기때문에 루트 노드인 최댓값 10을 가져옵니다.
pop_heap은 호출될 시, 부모노드를 맨 마지막 자식노드인 end와 교환하고 부모노드를 재정렬 합니다.
그리고 pop_back() 을 통해 컨테이너 내에서 마지막 노드를 빼내야 합니다.
pop_heap은 O(log N)의 복잡도를 가지며, pop_heap은 최대 2 log N 의 연산을 수행합니다.
<sort_heap>
sort_heap은 힙을 재정렬 합니다.
| 1 2 3 4 |
vector<int> nvt = { 1,2,3,4,5,6,7,8,9,10 }; std::make_heap(nvt.begin(), nvt.end()); random_shuffle(nvt.begin(), nvt.end()); std::sort_heap(nvt.begin(), nvt.end()); |
위 같이, 섞여버린 힙을 다시 sort_heap을 통해 재정렬합니다.
sort_heap은 최대 O(N log N)의 복잡도를 가지며, N lon N 만큼 연산을 수행합니다.
이러한 heap 연산 알고리듬을 사용하여 정렬을 수행하려면,
위의 make_heap(first, last)과 sort_heap(first, last)을 차례로 사용하거나, partial_sort(first, last, last)를 사용하면 됩니다.)
