2.5.1 힙 연산

이 절에서는 힙에서 사용되는 다양한 연산 동작에 대해 알아보겠습니다.

힙에 원소 삽입하기

힙의 가장 중요한 불변성은 완전 이진 트리를 유지해야 한다는 점입니다. 완전 이진 트리를 유지하고 있어야 배열 자료 구조를 이용하여 힙을 저장할 수 있습니다. 완전 이진 트리를 유지하는 힙에 새 원소를 삽입하려면 단순히 배열의 맨 마지막 위치에 원소를 추가하면 됩니다. 이 작업은 기존 트리의 마지막 레벨, 마지막 노드 바로 오른쪽에 새로운 노드를 추가하는 것과 같습니다. 만약 마지막 레벨이 꽉 차 있다면 새로운 레벨을 추가하여 노드를 추가합니다.

이번에는 다른 불변 조건에 대해 생각해보겠습니다. 모든 노드는 자식 노드보다 더 큰 값을 가지고 있어야 합니다. 일단 기존의 트리는 이미 이 불변 조건을 만족하고 있다고 가정하겠습니다. 그러나 새로운 원소를 트리의 맨 마지막 위치에 추가한 후에는 이 조건이 성립되지 않을 가능성이 생깁니다. 이를 해결하기 위해 새로 삽입한 원소의 부모 노드와 값을 비교하고, 만약 부모 노드가 더 작으면 서로 교환(swap)합니다. 만약 부모 노드에 다른 자식 노드가 있다 하더라도 이 자식 노드는 새로 추가한 원소보다 작습니다(새 원소 > 부모 노드 > 다른 자식 노드).