yg log --graph --oneline --all

Home Stack Notes AboutRSS

2. 힙은 한 경로만 고쳐도 된다

작성 · 4분 읽기 · 조회수 —수정

기초 개념과 예제를 보강하고 시리즈 흐름을 연결

최댓값을 반복해서 꺼내는 문제

우선순위 큐는 먼저 들어온 값보다 우선순위가 높은 값을 먼저 꺼내는 자료구조다. 최대 우선순위 큐라면 가장 큰 값을 먼저 꺼낸다. 힙은 이 연산을 빠르게 구현하는 완전이진트리다.

예를 들어 작업 우선순위가 4, 9, 2이고 새 작업 7이 들어온다고 하자. 입력 순서대로 저장만 하면 최댓값을 꺼낼 때마다 전체를 훑어야 한다. 내림차순을 계속 유지하면 꺼내기는 쉽지만 새 값의 자리를 만들며 여러 원소를 밀 수 있다. 최대 힙은 가장 큰 값만 루트에 두고 나머지는 부모와 자식 사이의 순서만 유지한다. 그래서 삽입과 최댓값 삭제가 모두 트리 높이만큼인 O(log n)에 끝난다.

완전이진트리는 위 레벨부터, 같은 레벨에서는 왼쪽부터 빈칸 없이 채운다. 그래서 포인터 없이 배열에 저장할 수 있다. 1번 인덱스를 루트로 쓰면 노드 i의 부모는 i/2, 자식은 2*i와 2*i+1이다. 최대 힙은 모든 간선에서 부모 >= 자식만 보장한다. 왼쪽과 오른쪽 형제의 대소관계나 배열 전체의 정렬은 보장하지 않는다.

배열:  [ -, 9, 7, 5, 2 ]
트리:       9
           / \
          7   5
         /
        2

OJ 60점 옆에 남은 의심

힙 실습 코드에는 날짜와 함께 짧은 주석이 남아 있다.

현재 문제가 있음 oj 60점, 아무래도 DownHeap에서 문제 발생하나봄

이 문장은 원인을 찾았다는 기록이 아니라 당시 DownHeap을 의심했다는 기록이다. 현재 남은 코드만으로 그 추측을 원인으로 확정할 수는 없다. 여기서는 올바른 DownHeap이 보장해야 하는 조건을 다시 따라간다.

삽입은 위로 한 경로만 본다

[9, 7, 5, 2]인 최대 힙에 12를 넣으면 새 값은 다음 빈 자리인 5번에 놓인다. 기존 노드끼리의 관계는 삽입 전부터 올바르다. 새로 깨질 수 있는 관계는 12와 부모 7, 그다음 부모 9뿐이다.

static void up_heap(int i) {
    while (i > 1 && heap[i] > heap[i / 2]) {
        swap(&heap[i], &heap[i / 2]);
        i /= 2;
    }
}

12와 7을 바꾸고, 다시 12와 9를 바꾸면 끝난다. 다른 가지는 새 값과 닿지 않았으므로 다시 검사할 이유가 없다. 노트에서 “추가된 노드와 그 부모를 비교하고, 부모에 대해 재귀적으로 시행”한다고 쓴 부분이 바로 이 경로를 가리킨다.

단계 배열의 유효 구간 확인한 관계
삽입 직후 9 7 5 2 12 새 노드 12와 부모 7에서 위반
첫 교환 9 12 5 2 7 12와 새 부모 9에서 위반
둘째 교환 12 9 5 2 7 루트에 도착해 종료

새 값을 다음 빈칸에 붙이면 기존 노드의 부모·자식 관계가 그대로 유지되어 새 노드의 조상 경로만 고치면 된다. 배열 중간에 끼워 넣어 다른 원소의 인덱스까지 바꾸면 여러 부모·자식 관계가 함께 달라진다.

삭제는 더 큰 자식 쪽으로 내려간다

최댓값을 꺼내면 루트가 빈다. 저장소 구현은 마지막 값을 루트로 옮겨 완전이진트리 모양을 먼저 복구한다. 이제 깨질 수 있는 곳은 새 루트에서 아래로 이어지는 한 경로다.

static void down_heap(int i) {
    while (2 * i <= size) {
        int child = 2 * i;
        if (child + 1 <= size && heap[child + 1] > heap[child]) child++;
        if (heap[i] >= heap[child]) break;
        swap(&heap[i], &heap[child]);
        i = child;
    }
}

여기서 두 자식 중 더 큰 쪽을 골라야 한다. 작은 자식과만 바꾸면 큰 자식이 부모보다 큰 상태가 남을 수 있다. 자식이 하나뿐인 경우에는 왼쪽 자식만 비교해야 한다. DownHeap의 정확성은 자식 존재 범위와 더 큰 자식 선택을 모두 만족해야 한다.

앞에서 만든 12 9 5 2 7에서 12를 꺼내 보자. 마지막 값 7을 루트로 옮긴 뒤 크기를 하나 줄이면 유효 힙은 7 9 5 2다.

단계 배열의 유효 구간 판단
루트 대체 7 9 5 2 두 자식 9와 5 중 9가 더 큼
7과 9 교환 9 7 5 2 7은 남은 자식 2보다 크므로 종료

여기서 작은 자식 5와 바꾸면 5 9 7 2가 되어 루트 5보다 자식 9가 크다. 이 반례가 “아무 자식이나”가 아니라 더 큰 자식을 골라야 하는 이유를 보여 준다.

노트에는 “remove는 root 제거이므로 O(1)”이라는 문장도 있다. 루트 값을 읽는 일만 보면 O(1)이다. 그러나 우선순위 큐의 삭제 연산은 모양과 힙 순서를 복구해야 끝난다. 완전이진트리의 높이가 O(log n)이므로 removeMax 전체는 O(log n)이다.

이번에 다시 확인한 불변식

이번에는 원본을 고쳐 썼다고 가정하지 않고, 별도의 재현 코드를 만들었다. 4, 9, 1, 7, 7, 12, 3을 차례로 삽입하고 매번 모든 부모·자식 관계를 검사했다. 이후 최댓값을 연속으로 꺼내 12, 9, 7, 7, 4, 3, 1과 같은지도 확인했다.

검사는 통과했다. 이것이 과거 OJ 60점의 원인을 밝혔다는 뜻은 아니다. 당시 입력과 채점 명세가 없기 때문에 그 원인은 여전히 미해결이다. 지금 확인한 것은 올바른 UpHeap과 DownHeap이 지켜야 할 계약이다. 한 번의 변경이 한 자리에서 시작되므로, 그 자리에서 루트 또는 리프까지 이어지는 한 경로만 고치면 충분하다.

참고한 기록과 코드

관련 포스트