더북(TheBook)

3.5.2 힙 연산

힙은 컨테이너가 아니고 컨테이너 안에 저장된 원소들의 특정 구조를 뜻하는 것이므로 힙은 범위, 즉 시작 반복자와 끝 반복자로만 확인할 수 있다. 컨테이너에 있는 원소들의 일부 순차열로도 힙을 만들 수 있다는 뜻이다. 힙을 생성한 후에는 원소들을 추가하고 싶을 것이다. algorithm 헤더의 push_heap() 템플릿 함수가 원소를 추가하지만, push_heap() 함수가 동작하는 방식을 처음 보면 약간 이상하게 보일지도 모른다. 힙에 원소를 추가하려면 순차열에서 동작하는 메서드를 이용해 원소를 순차열의 뒤에 추가해야 한다. 그다음에 뒤에 추가한 마지막 원소를 처리하기 위해 push_heap() 함수를 호출한다. push_heap() 함수는 힙 배치를 유지하기 위해 순차열의 적절한 위치에 원소를 삽입한다.

std::vector<double> numbers { 2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers)); // 결과: 12 10 3.5 6.5 8 2.5 1.5 6
numbers.push_back(11);                                  // 결과: 12 10 3.5 6.5 8 2.5 1.5 6 11
std::push_heap(std::begin(numbers), std::end(numbers)); // 결과: 12 11 3.5 10 8 2.5 1.5 6 6.5

주석은 각 연산이 numbers 원소들의 배치에 어떤 영향을 주었는지 보여준다. 힙에 원소를 추가하는 과정은 이런 방식으로 동작한다. 컨테이너에 새 원소 추가는 함수 멤버 호출로만 할 수 있다. 즉, 반복자로 지정한 범위를 받는 함수에는 원소를 추가하는 기능이 없다. push_back()은 순차열의 끝에 원소를 추가하고, push_heap()은 힙 정렬을 복구한다. push_heap()을 호출하는 것으로 힙에 원소가 추가되었고, 힙 정렬이 깨졌을지도 모른다고 알린다. 따라서 push_heap() 함수는 마지막 원소가 새로 추가된 원소라 가정하고, 힙을 유지하기 위해 순차열의 원소들을 재배열한다. 결과를 보면 여기서는 재배치가 크게 일어났음을 알 수 있다. 또한, 순차열을 힙으로 구성했으므로 원소 전체가 내림차순으로 정렬되어 있지 않다는 것도 알 수 있다. 우선순위 큐가 힙이지만, 힙에 저장된 원소들의 순서가 우선순위 큐에 저장된 순서와 반드시 일치하는 것도 아니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.