루트 노드는 12이고, 자식 노드는 10과 3.5이다. 값이 10인 원소의 자식 노드는 값 6.5와 8이고, 값이 3.5인 원소의 자식 노드는 2.5와 1.5이다. 값이 6.5인 원소는 값이 6인 잎 노드 하나만 갖는다.

priority_queue가 바로 힙이다! priority_queue의 인스턴스는 내부에서 힙을 생성한다. 이게 그림 3-3에서 원소들이 기반 컨테이너에 정렬된 상태를 반영하지 않아도 된다고 한 이유다. 힙에서는 이어지는 모든 원소 쌍에 같은 비교 관계가 반드시 적용되는 것은 아니다. 그림 3-5에서 힙에 있는 처음 세 개의 원소는 내림차순이지만, 네 번째 원소(6.5)는 세 번째 원소(3.5)보다 크다. 그렇다면 왜 STL에는 이미 힙인 priority_queue와 힙을 생성할 수 있는 두 가지 기능이 있을까? 힙을 우선순위 큐로 사용하면 되지 않을까?

사실, priority_queue는 힙보다 장점이 있다. 원소 순서가 자동으로 관리된다. 우선순위 큐는 첫 번째 원소만 접근할 수 있고 다른 원소에는 접근할 수 없으므로 priority_queue의 정렬된 상태를 망가뜨릴 수 없다. 원하는 것이 우선순위 큐라면 이는 큰 장점이 된다. 반면에 make_heap()으로 힙을 생성하면 priority_queue에 없는 몇 가지 장점이 있다.

• 힙에서는 가장 큰 원소뿐 아니라 어떤 원소에도 접근할 수 있다. 이는 직접 생성한 벡터 같은 컨테이너에 원소들을 저장하기 때문에 가능하다. 어떤 원소에도 접근할 수 있으므로 원소들의 순서 일관성을 훼손할 가능성도 있지만, make_heap()을 호출해서 언제든지 복구할 수 있다.

• 랜덤 액세스 반복자를 지원하는 어떤 시퀀스 컨테이너로도 힙을 생성할 수 있다. 일반 배열, string 객체, 직접 정의한 컨테이너가 여기에 해당한다. 즉, 필요할 때 순차열 컨테이너의 원소들을 힙으로 배열할 수 있고, 필요하다면 반복해서 힙으로 배열할 수 있다는 뜻이다. 또한, 원소들의 부분집합도 힙으로 배열할 수 있다.

• 힙 순서를 유지하는 힙 함수를 사용한다면 힙을 우선순위 큐로 쓸 수 있다.