완전이진트리를 사용하는 이유는 무엇인가요?

코딩 테스트 문제를 푸시다가 Heap이라는 자료 구조에 대해서 궁금해지셨군요. 우선 Heap은 최소값이나 최대값에 접근하는데 최적화된 자료구조입니다. 이미 값들이 Heap 저장되어 있는 상태에서 O(1), 즉 상수 시간에 최소값이나 최대값을 얻을 수 있죠. 이 것이 가능한 이유는 Heap이 최소/대값을 트리의 루트(root)에 놓기 때문입니다. 하지만 이를 위해서는 Heap은 내부 구조를 항상 최소/대값을 제공하기 위한 최적의 상태로 유지해야하는데요. 다시 말해서 Heap에 값을 추가하거나 삭제할 때 마다 내부적으로 트리 노드의 재배치가 필요합니다. 보통 Heap을 완전 이진 트리의 형태로 구현하는 이유는 값을 추가하거나 삭제하는데 들어가는 비용을 O(log(n))으로 제한할 수 있기 때문입니다. 이 것은 완전 이진 트리의 높이가 log₂(n)이기 때문이죠. 만약에 Heap이 완전 이진 트리의 형태로 내부 구조를 유지하지 않는다면 값을 추가하거나 삭제하는데 들어가는 비용이 어떻게 될까요? 최악의 경우 마치 링크드 리스트처럼 왼쪽에만 자식이 달리거나 오른쪽으로만 자식이 달릴 수도 있을테니 O(n), 즉 선형 시간에 가까워질 것입니다. 그럴러면 뭐하러 애초에 Heap을 사용할까요? 단순하게 주어진 값들을 처음부터 끝까지 탐색해도 O(n) 시간에 최소/대값을 찾을 수 있는데 말이죠. Heap에서 추가한 값이 최소/대값이어서 트리의 루트로 끌어 올려야하거나, 헤드에 있는 최소/대값을 삭제한 후에 내부적으로 일어나야하는 트리 노드의 재배치를 머리 속으로 생각해보시거나 한 번 종이에 그려보시면 더 이해가 잘 되실 거에요. 답변이 도움이 되었으면 좋겠습니다.