2.5 힙
1장에서 std::priority_queue를 설명하면서 힙(heap)이 무엇인지에 대해 간략히 설명했습니다. 이 장에서는 힙에 대해 좀 더 깊이 있게 알아보려고 합니다. 복습의 의미로, 힙은 다음과 같은 시간 복잡도를 만족해야 합니다.
• O(1): 최대 원소에 즉각적으로 접근할 수 있어야 합니다.
• O(log N): 원소 삽입에 대한 시간 복잡도
• O(log N): 최대 원소 삭제에 대한 시간 복잡도
원소 삽입 또는 삭제에 대해 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 합니다. 다만 이 경우에는 특히 완전 이진 트리(complete binary tree)를 사용해야 합니다. 완전 이진 트리는 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드가 있는 트리입니다. 그림 2-14는 완전 이진 트리와 불완전 이진 트리의 예를 보여줍니다.
▲ 그림 2-14 완전 이진 트리와 불완전 이진 트리