힙(Heap)이란?

힙은 완전이진트리의 형태를 가지며, 노드 간의 대소 관계가 특정 조건을 만족하는 자료구조이다. 배열 상에서 특정 규칙에 따라 요소들이 배치되며, 이를 통해 최댓값 또는 최솟값을 빠르게 접근할 수 있다. 힙은 두 가지 유형으로 나뉜다:

• 최대힙(Max Heap): 각 부모 노드의 값이 자식보다 크거나 같다.
• 최소힙(Min Heap): 각 부모 노드의 값이 자식보다 작거나 같다.

힙의 핵심 성질

1. 항상 완전이진트리(Complete Binary Tree) 구조를 따른다. 즉, 마지막 레벨을 제외하고 모든 레벨이 가득 차 있으며, 마지막 레벨은 왼쪽부터 순차적으로 채워진다.
2. 부모-자식 간의 우선순위 관계가 유지된다. 이는 삽입 및 삭제 연산 후에도 반드시 복원되어야 한다.

논리적 구조와 물리적 저장 방식

힙은 논리적으로는 트리 구조이지만, 실제로는 일차원 배열을 사용하여 효율적으로 저장된다. 완전이진트리는 비어 있는 공간이 없기 때문에 배열 인덱스를 통해 부모와 자식 노드 간의 위치를 쉽게 계산할 수 있다.

배열 인덱스 기준으로 다음과 같은 관계가 성립한다 (루트 인덱스 = 0 기준):

• 노드 i의 왼쪽 자식 인덱스: 2*i + 1
• 노드 i의 오른쪽 자식 인덱스: 2*i + 2
• 노드 i의 부모 인덱스: (i - 1) / 2

이러한 수학적 관계 덕분에 포인터 없이도 트리 탐색이 가능하며, 메모리 사용도 최적화된다.

힙 생성 전제 조건

힙 연산을 수행하기 위해서는 특정 조건이 충족되어야 한다. 특히 아래에서 설명할 두 가지 주요 구성 방법은 각각 다른 초기 상태를 요구한다.

방법 1: 위로 조정 (Upward Adjustment)

새로운 요소가 배열 끝에 추가된 후, 해당 요소가 올바른 위치에 도달할 때까지 부모와 비교하며 위로 이동시키는 방식이다. 이 방법은 다음과 같은 조건에서 유효하다:

• 삽입 전 배열이 이미 유효한 힙 상태여야 한다.
• 새로운 요소는 리프 노드에 위치하므로, 영향을 받는 경로는 그 조상들만이다.

왜 삽입 전 상태가 힙이어야 하는가?

Upward adjustment 알고리즘은 "현재 삽입된 노드 외에는 모두 힙 조건을 만족한다"는 가정 하에 동작한다. 이 가정이 깨지면, 단일 경로 조정만으로 전체 구조를 회복할 수 없으며, 잘못된 결과를 초래할 수 있다.

코드 예시: 최소힙 기준 위로 조정

void swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void heapifyUp(int arr[], int childIndex) {
    while (childIndex > 0) {
        int parentIndex = (childIndex - 1) / 2;
        if (arr[childIndex] < arr[parentIndex]) {
            swap(&arr[childIndex], &arr[parentIndex]);
            childIndex = parentIndex;  // 자식 인덱스를 먼저 갱신
        } else {
            break;
        }
    }
}

이 코드에서 childIndex를 먼저 갱신하는 이유는, 다음 반복에서 새로운 부모를 정확히 찾기 위해서이다. 만약 부모 값을 먼저 수정하면, 원래의 계층 구조 정보를 잃게 되고, 잘못된 비교가 발생할 수 있다. 따라서 자식 → 부모 순으로 인덱스를 업데이트하는 것이 안전하다.

방법 2: 아래로 조정 (Downward Adjustment)

루트 노드가 힙 조건을 위반했을 때 사용되는 방법이다. 일반적으로 루트 삭제 후 마지막 요소를 루트에 배치하고, 아래 방향으로 적절한 위치를 찾아 내려가는 방식이다. 이 방식은 다음과 같은 조건에서 시작해야 한다:

• 해당 노드의 왼쪽과 오른쪽 서브트리가 각각 유효한 힙이어야 한다.
• 조정은 리프가 아닌 내부 노드 중 가장 마지막 비리프 노드부터 역순으로 수행된다.

왜 부모를 먼저 이동시키는가?

아래로 조정 과정에서 부모 인덱스를 먼저 갱신한 후 자식을 재계산하는 것은 자연스러운 흐름이다. 현재 부모 위치가 자식의 위치를 결정하므로, 부모를 갱신하면 자식은 자동으로 2*parent + 1 또는 2*parent + 2로 다시 계산되어야 한다. 이는 위로 조정과 마찬가지로, 상태 일관성을 유지하기 위한 필수 절차이다.

코드 예시: 최대힙 기준 아래로 조정

void heapifyDown(int arr[], int parentIdx, int size) {
    int leftChild = 2 * parentIdx + 1;

    while (leftChild < size) {
        int targetChild = leftChild;
        int rightChild = leftChild + 1;

        // 오른쪽 자식이 존재하고 더 크면 선택
        if (rightChild < size && arr[rightChild] > arr[leftChild]) {
            targetChild = rightChild;
        }

        // 자식이 부모보다 크면 교환
        if (arr[targetChild] > arr[parentIdx]) {
            swap(&arr[targetChild], &arr[parentIdx]);
            parentIdx = targetChild;
            leftChild = 2 * parentIdx + 1;
        } else {
            break;
        }
    }
}

// 전체 배열을 힙으로 구성
void buildMaxHeap(int arr[], int n) {
    // 마지막 비리프 노드부터 시작 (n/2 - 1)
    for (int i = (n - 2) / 2; i >= 0; i--) {
        heapifyDown(arr, i, n);
    }
}

여기서 buildMaxHeap 함수는 배열의 절반 지점부터 시작하여 역순으로 각 노드에 대해 heapifyDown을 적용한다. 이는 모든 서브트리가 힙 조건을 만족하도록 보장하며, 전체 시간 복잡도는 O(n)이다.