[43] - Heap Operations

자료구조나 알고리즘에서 등장하는 heap이 맞습니다. Memory의 heap을 가리키는 말이 아닙니다. 당시에 배웠던 heap의 성질에는 다양한 것들이 있는데 그 중에 기억해야 할 것 중 하나는 heap의 최상단에 가장 큰 값이 오는 max heap, 반대의 min heap이 존재한다는 것입니다. heap은 주로 tree의 형태로 개념화/상징화 됩니다. 이것은 Data Structure에서 더 자세히 다루기 때문에 여기서 할 필요는 없을 것 같습니다.

Data structure를 공부하면서 배우는게 낫지만 heap이 중요한 이유는 이를 바탕으로 priority queue를 만들 수 있다는 점입니다. 특히 알아두면 좋은 것이 'A-star pathfinding' Algorithm에서도 쓰이며 heap-sort역시 heap에 의지합니다.

std::make_heap

어떤 범위의 컨테이너에 대해서 Max heap을 만들어줍니다. 만약 min heap을 만들고 싶다면 compare부분에 적당한 Functor를 넣어주면 됩니다.

compare operator를 넣어서 min heap을 만듭니다

이것이 heap인지 아닌지 알 수 있는 함수도 있습니다. std::is_heap

true를 반환합니다.

std::push_heap, std::pop_heap

작동방법이 직관적이지 않습니다. 보기에는 일단 만들어 둔 heap에 대해서 곧장 호출하면 될 것 같지만 그렇게 하는 것보다는 heap이 된 컨테이너에 대해서 push를 수행하고 나서 std::push_heap을 호출해주는 게 낫습니다. 아래와 같은 코드에서는 컨테이너에 격납될 값의 최대가 99보다 클 수 없기 때문에 100을 추가한다면 무조건 머리에 올 것입니다. 새롭게 만든 heap에 대해서 std::is_heap을 하면 true가 나옵니다.

실제로 100이 가장 위에 추가된 모습입니다.

그렇다면 std::pop_heap은 더 간단합니다. 가장 큰/작은 값을 반환하기 때문입니다. 따라서 별도의 과정 없이 호출하면 논리에 따라 알맞은 값이 제거됩니다. 제대로 사라지는지 아닌지 확인하고 싶으면 std::pop_heap이후에 컨테이너 가장 끝의 값을 보면 됩니다.

std::pop_heap이 컨테이너의 크기까지 줄이진 않습니다

그렇다면 이 std::pop_heap을 계속 반복하여 컨테이너에 격납된 요소들에 대해 한 번씩 모두 시행하면 정렬된 컨테이너를 얻을 수 있을 것입니다. std::sort_heap과 완전히 같은 기능을 할 것입니다.