방송대 자료구조 9강 : 우선순위 큐와 최소 힙의 삭제·삽입

방송대 자료구조 9강: 우선순위 큐와 최소 힙의 삭제·삽입

먼저 들어온 항목보다 더 급한 항목을 먼저 처리해야 한다면 일반 큐의 순서만으로는 부족합니다. 이 글은 우선순위 큐가 왜 힙을 필요로 하는지부터 시작해, 최소 힙의 배열이 유효한지 판정하고, 루트 삭제 때 아래로 내려가는 값과 삽입 때 위로 올라가는 값을 단계별로 추적하도록 돕습니다.

먼저 온 순서와 먼저 처리할 순서가 다를 수 있다

일반 큐는 먼저 들어온 데이터가 먼저 삭제되는 선입선출 구조입니다. 준비 큐에 A, B, C가 그 순서로 들어왔다면 우선순위를 따로 고려하지 않는 큐에서는 A가 먼저 나옵니다. 그러나 각 항목에 처리 우선순위가 있고 C가 가장 높은 우선순위를 가진다면 도착 순서와 관계없이 C를 먼저 선택해야 합니다.

우선순위 큐(priority queue)는 대기 항목 가운데 우선순위가 가장 높은 항목을 먼저 삭제하는 추상 자료형입니다. 강의자료의 수치 예에서는 작은 값을 높은 우선순위로 해석해 가장 작은 값을 삭제합니다. 따라서 ‘앞에 있는 값’과 ‘다음에 삭제할 값’이 항상 같은 것은 아닙니다.

판단 출발점: 도착 시각이 처리 순서를 정하면 일반 큐가 맞고, 각 항목의 우선순위 키가 처리 순서를 정하면 우선순위 큐가 맞습니다. 최소 힙은 작은 키를 먼저 꺼내는 우선순위 큐를 구현하는 대표 구조입니다.

배열 우선순위 큐는 삭제할 값을 찾는 과정이 필요하다

강의자료의 배열 예는 front와 rear 사이에 1, 5, 4, 2, 6을 저장합니다. 삽입은 rear 쪽 빈 칸에 값을 추가할 수 있지만, 삭제할 때는 현재 값 전체에서 가장 작은 값을 찾아야 합니다. 저장 순서가 5, 4, 2, 6, 3처럼 정렬되어 있지 않아도 우선순위 판정만 정확하면 동작하지만, 다음 삭제 대상을 찾기 위한 비교가 필요합니다.

연산	일반 큐의 기준	강의의 우선순위 큐 기준	확인해야 할 것
삽입	rear에 추가	배열의 새 위치에 추가	저장 순서 자체가 우선순위 순서일 필요는 없음
삭제	front의 값 제거	저장된 값 중 최솟값 제거	삭제 전에 다음 최솟값을 판별해야 함
결과 순서	도착 순서	키의 우선순위 순서	같은 입력이라도 삭제 결과가 달라질 수 있음

예를 들어 현재 값이 5, 4, 2, 6, 3이라면 앞쪽의 5가 아니라 2가 삭제 대상입니다. 3을 새로 넣어도 2가 남아 있는 동안에는 2가 다음 삭제 대상입니다. 우선순위 큐에서는 삽입 위치보다 ‘어느 값이 가장 높은 우선순위인가’를 빠르게 알아내는 구조가 중요합니다.

오개념 교정: 우선순위 큐를 값이 완전히 정렬된 배열과 같다고 생각하면 안 됩니다. 추상 자료형이 요구하는 것은 최고 우선순위 항목을 올바르게 선택하는 일이며, 나머지 항목 전체의 정렬은 필수 조건이 아닙니다.

힙은 전체 정렬 대신 모양과 부모·자식 관계를 지킨다

힙(heap)은 완전 이진 트리의 모양을 가지면서 부모와 자식 사이에 일정한 대소 관계를 유지하는 구조입니다. 완전 이진 트리는 마지막 레벨을 제외한 레벨이 모두 채워지고, 마지막 레벨은 왼쪽부터 빈틈없이 채워집니다. 이 모양 덕분에 트리를 배열에 연속해서 저장할 수 있습니다.

최소 힙에서는 모든 부모가 자신의 자식보다 작거나 같고, 최대 힙에서는 모든 부모가 자신의 자식보다 크거나 같습니다. 이 규칙이 트리의 모든 간선에서 성립하면 최소 힙의 루트는 전체 최솟값, 최대 힙의 루트는 전체 최댓값이 됩니다.

힙의 추상 자료형은 데이터를 넣는 insert, 루트의 최고 우선순위 데이터를 제거하는 delete, 제거하지 않고 루트 값을 읽는 peek, 공백 여부를 확인하는 isEmpty, 저장 개수를 확인하는 size 연산으로 정리할 수 있습니다. peek와 delete는 모두 루트를 대상으로 하지만, peek는 힙의 크기와 배열을 바꾸지 않는다는 차이가 있습니다.

판정 대상	최소 힙	최대 힙	공통으로 요구되는 것
루트	전체 최솟값	전체 최댓값	최고 우선순위 항목
부모와 자식	부모 ≤ 자식	부모 ≥ 자식	모든 부모·자식 쌍에서 관계 성립
형태	완전 이진 트리	완전 이진 트리	마지막 레벨을 왼쪽부터 채움
형제 사이	별도 정렬 조건 없음	별도 정렬 조건 없음	부모와의 관계만 검사

최소 힙의 왼쪽 자식이 오른쪽 자식보다 작아야 한다는 규칙은 없습니다. 또한 왼쪽 서브트리의 모든 값이 오른쪽 서브트리의 모든 값보다 작을 필요도 없습니다. 힙은 이진 탐색 트리의 좌우 정렬 규칙이 아니라 각 부모와 자식 사이의 우선순위 관계를 사용합니다.

힙 판정은 모양 검사와 간선 검사를 분리한다

트리 그림이 주어졌을 때 루트가 가장 작다는 사실만 보고 최소 힙이라고 결론 내리면 부족합니다. 먼저 완전 이진 트리인지 확인하고, 그다음 모든 부모·자식 간선을 검사해야 합니다.

1. 모양: 마지막 레벨 이전이 모두 채워졌는지, 마지막 레벨의 노드가 왼쪽부터 연속해 있는지 확인합니다.
2. 루트 방향: 문제에서 최소 힙인지 최대 힙인지 정합니다.
3. 간선: 최소 힙이면 각 부모가 두 자식보다 작거나 같은지, 최대 힙이면 크거나 같은지 검사합니다.
4. 불필요한 조건 제거: 형제의 좌우 크기나 서브트리 전체 정렬을 힙 조건에 넣지 않습니다.

학습을 위해 구성한 배열 [3, 8, 6, 14, 11, 9, 17]을 1번 인덱스부터 저장했다고 합시다. 부모 3은 자식 8과 6보다 작고, 부모 8은 14와 11보다 작으며, 부모 6은 9와 17보다 작습니다. 배열이 완전 이진 트리의 레벨 순서에 대응하므로 이 배열은 최소 힙입니다.

반면 [3, 8, 6, 14, 2, 9, 17]은 모양은 같지만 인덱스 2의 부모 8이 자식 2보다 큽니다. 루트 3이 대부분의 값보다 작아 보이더라도 간선 하나가 규칙을 어기므로 최소 힙이 아닙니다.

1번 인덱스를 루트로 두면 이동 경로를 계산할 수 있다

강의자료는 배열의 0번 칸을 비워 두고 루트를 1번에 저장합니다. 노드의 인덱스를 i라고 하면 왼쪽 자식은 2i, 오른쪽 자식은 2i+1, 부모는 정수 나눗셈 i/2로 찾습니다. 이 관계가 포인터 없이도 부모와 자식을 오갈 수 있게 합니다.

현재 인덱스 i	부모 i/2	왼쪽 자식 2i	오른쪽 자식 2i+1
1	없음	2	3
3	1	6	7
5	2	10	11
6	3	12	13

예를 들어 인덱스 6의 부모는 6/2=3이고 자식 후보는 12와 13입니다. 다만 자식 인덱스가 현재 size보다 크면 실제 노드는 없습니다. 공식을 계산하는 것과 배열 범위 안에 노드가 존재하는지를 확인하는 것은 별개의 단계입니다.

완전 이진 트리는 레벨 순서로 저장했을 때 중간 빈칸이 생기지 않으므로 배열 공간을 연속적으로 사용할 수 있습니다. 별도의 링크 필드 없이 위 인덱스 계산으로 이동할 수 있다는 점이 강의자료에서 배열 구현의 실행·기억장소 측면 장점으로 제시됩니다.

배열 검산: 인덱스 1부터 size까지 빈칸 없이 값이 있고, 각 i>1에서 최소 힙이면 heap[i/2] <= heap[i]가 성립해야 합니다.

루트 삭제는 마지막 값을 아래로 내려 빈자리를 메운다

최소 힙에서 삭제 대상은 루트의 최솟값입니다. 루트를 제거하면 완전 이진 트리의 첫 칸이 비므로, 마지막 노드를 임시 값 temp로 꺼내 루트 자리부터 내려보냅니다. 이때 두 자식 중 더 작은 자식을 골라 위로 올려야 최소 힙 관계가 유지됩니다.

1. 루트 값을 반환용 data에 보관합니다.
2. 마지막 값을 temp에 보관하고 size를 1 줄입니다.
3. 루트에서 시작해 두 자식 중 더 작은 자식을 선택합니다.
4. temp가 선택한 자식보다 작거나 같으면 그 자리에서 멈춥니다.
5. 그렇지 않으면 작은 자식을 부모 자리로 올리고 한 레벨 아래에서 반복합니다.
6. 멈춘 자리에 temp를 저장합니다.

다음 코드는 강의자료의 최소 힙 삭제 핵심 흐름을 들여쓰기와 조건이 드러나도록 정리한 것입니다. 호출 전 힙이 비어 있지 않다는 전제가 필요합니다.

typedef struct heap {
    int heap[MAX_SIZE];
    int size;
} heap;

int min_heapDelete(heap *h) {
    int parent = 1;
    int child = 2;
    int data = h->heap[1];
    int temp = h->heap[(h->size)--];

    while (child <= h->size) {
        if (child < h->size &&
            h->heap[child] > h->heap[child + 1]) {
            child++;
        }
        if (temp <= h->heap[child]) {
            break;
        }
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return data;
}

child < h->size는 오른쪽 자식이 실제로 있을 때만 두 자식을 비교하게 합니다. 자식이 하나뿐이면 왼쪽 자식을 그대로 선택합니다. 이 경계 조건을 빼면 배열 범위 밖의 오른쪽 칸을 읽을 수 있습니다.

삭제 예제는 선택한 자식과 임시 값의 비교를 따로 적는다

앞에서 확인한 학습용 최소 힙 [3, 8, 6, 14, 11, 9, 17]에서 루트 3을 삭제해 봅시다. 마지막 값 17을 temp로 꺼내고 크기를 6으로 줄입니다.

단계	부모 자리	실제 자식	선택과 이동	남은 temp
시작	인덱스 1	8(2), 6(3)	작은 자식 6을 루트로 올림	17
다음 레벨	인덱스 3	9(6), 오른쪽 없음	17>9이므로 9를 인덱스 3으로 올림	17
종료	인덱스 6	없음	빈 인덱스 6에 17 저장	저장 완료

최종 배열은 [6, 8, 9, 14, 11, 17]입니다. 검산하면 6≤8, 6≤9, 8≤14, 8≤11, 9≤17이 모두 성립합니다. 두 자식 중 8을 먼저 올렸다면 루트 아래에 더 작은 6이 남아 최소 힙 관계가 즉시 깨집니다.

강의자료의 예에서는 루트 1을 삭제하고 마지막 값 23을 내립니다. 15와 5 중 5, 이어 10과 19 중 10, 이어 12 하나를 차례로 올린 뒤 23을 저장합니다. 최종 레벨 순서는 [5, 15, 10, 20, 16, 12, 19, 25, 30, 17, 18, 23]입니다.

말단 삽입은 부모보다 작을 동안 위로 올라간다

삽입은 삭제의 반대 방향으로 진행합니다. 완전 이진 트리의 모양을 지키기 위해 새 값의 후보 자리를 배열 마지막에 만들고, 부모보다 작은 동안 부모를 아래로 복사하며 빈자리를 위로 옮깁니다. 루트에 도달하거나 부모가 새 값보다 작거나 같으면 멈춥니다.

강의자료의 삽입 흐름을 정리한 코드는 다음과 같습니다. 호출 전 배열에 새 값을 저장할 공간이 있다는 전제가 필요합니다.

void min_heapInsert(heap *h, int data) {
    int i = ++(h->size);

    while (i != 1 && data < h->heap[i / 2]) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = data;
}

강의의 삭제 결과 배열에 7을 삽입하면 새 후보 위치는 인덱스 13입니다. 부모 인덱스 6의 값 12를 13으로 내리고, 부모 인덱스 3의 값 10을 6으로 내립니다. 다음 부모는 루트의 5이며 7<5가 거짓이므로 인덱스 3에 7을 둡니다. 최종 배열은 [5, 15, 7, 20, 16, 10, 19, 25, 30, 17, 18, 23, 12]입니다.

이동과 교환의 차이: 강의 코드는 매 단계마다 새 값과 부모를 직접 교환하지 않습니다. 부모 값을 아래 빈자리로 복사해 통로를 만들고, 마지막에 새 값을 한 번 저장합니다. 추적할 때는 ‘현재 빈자리의 인덱스’를 기록하면 중복 저장처럼 보이는 중간 상태를 이해하기 쉽습니다.

같은 예제에 삽입을 이어 붙이면 두 방향이 대비된다

직접 구성한 삭제 결과 [6, 8, 9, 14, 11, 17]에 값 5를 삽입해 봅시다. 새 후보 위치는 인덱스 7이고 그 부모는 인덱스 3의 9입니다.

1. 5<9이므로 9를 인덱스 7로 내리고 빈자리를 인덱스 3으로 옮깁니다.
2. 인덱스 3의 부모는 인덱스 1의 6입니다. 5<6이므로 6을 인덱스 3으로 내립니다.
3. 빈자리가 루트 인덱스 1에 도달했으므로 5를 저장합니다.

최종 배열은 [5, 8, 6, 14, 11, 17, 9]입니다. 삭제에서는 두 자식 중 더 우선인 값을 선택하며 아래로 내려가고, 삽입에서는 부모 하나와 비교하며 위로 올라갑니다. 두 연산 모두 완전 이진 트리의 모양은 마지막 노드를 이용해 먼저 보존하고, 부모·자식 대소 관계만 복구합니다.

방향 판정: 최소 힙 삭제는 마지막 값이 루트에서 시작해 ‘더 작은 자식’을 따라 아래로 이동하고, 삽입은 새 값이 말단에서 시작해 ‘자신보다 큰 부모’를 따라 위로 이동합니다.

힙 연산의 오류는 비교 대상과 경계에서 찾는다

힙 문제의 결과가 틀렸다면 대입문보다 먼저 어떤 값을 비교했는지 확인합니다.

흔한 잘못	왜 실패하는가	교정 기준
삭제에서 항상 왼쪽 자식 선택	오른쪽 자식이 더 작으면 그 값을 건너뜀	두 자식이 있으면 더 작은 자식을 먼저 선택
오른쪽 자식 존재를 확인하지 않음	마지막 부모에 왼쪽 자식만 있을 수 있음	child < size일 때만 child+1 비교
삽입 값을 처음부터 배열 끝에 확정 저장	부모보다 작아도 위로 올라갈 빈자리가 없음	후보 위치를 만든 뒤 부모를 내려 보내고 마지막에 저장
루트만 확인해 힙 판정	아래 레벨의 부모·자식 관계가 깨질 수 있음	완전성 확인 후 모든 간선을 검사
배열 0번을 루트로 계산	강의 코드의 2i, 2i+1 관계와 어긋남	이 구현에서는 루트가 인덱스 1임을 먼저 표시

특히 삭제 코드의 temp <= heap[child]는 이동 종료 조건입니다. temp가 선택한 작은 자식보다 작거나 같다면 다른 자식보다도 작거나 같으므로 그 자리에 놓아도 됩니다. 반대로 조건을 temp >= heap[child]로 뒤집으면 아직 내려가야 할 큰 값이 너무 일찍 멈출 수 있습니다.

새 힙 문제는 자리·방향·관계의 순서로 푼다

새로운 배열과 연산이 주어지면 다음 흐름을 사용합니다.

1. 자리: 루트 인덱스와 size를 표시하고, 부모·자식 인덱스가 실제 범위에 있는지 확인합니다.
2. 구조: 배열이 완전 이진 트리의 레벨 순서를 나타내는지 확인합니다.
3. 관계: 최소·최대 힙 중 어느 규칙인지 정하고 모든 부모·자식 쌍을 검사합니다.
4. 방향: 삭제면 마지막 값을 루트에서 아래로, 삽입이면 새 값을 말단에서 위로 이동시킵니다.
5. 비교 대상: 삭제는 두 자식 중 더 우선인 쪽, 삽입은 현재 부모 하나를 선택합니다.
6. 검산: 값의 개수가 연산에 맞게 변했는지, 배열에 빈틈이 없는지, 모든 간선이 힙 관계를 만족하는지 다시 확인합니다.

이 순서는 결과 배열을 외우는 방법이 아니라 어떤 힙에도 적용할 수 있는 풀이 절차입니다. 루트 삭제와 말단 삽입은 이동 방향은 반대지만, 완전 이진 트리의 모양을 지킨 채 깨진 한 경로의 부모·자식 관계만 복구한다는 공통 원리를 가집니다.

핵심 개념 정리

• 우선순위 큐: 도착 순서가 아니라 우선순위 키가 가장 높은 항목을 먼저 삭제합니다.
• 힙의 두 조건: 완전 이진 트리의 모양과 모든 부모·자식 사이의 대소 관계를 함께 만족해야 합니다.
• 배열 관계: 루트가 1일 때 부모는 i/2, 자식은 2i와 2i+1입니다.
• 최소 힙 삭제: 루트를 반환하고 마지막 값을 더 작은 자식 경로로 내려보냅니다.
• 최소 힙 삽입: 말단 후보 자리에서 시작해 새 값보다 큰 부모를 아래로 보내며 올라갑니다.

힙 문제에서는 먼저 인덱스 1과 현재 크기를 표시하고 완전 이진 트리의 자리를 확인하세요. 그다음 최소·최대 방향을 정해 부모·자식 관계를 검사합니다. 삭제라면 작은 자식을 고르며 아래로, 삽입이라면 부모와 비교하며 위로 이동한 뒤, 마지막에는 노드 수·빈틈·모든 간선을 다시 확인하면 코드와 그림을 같은 기준으로 검산할 수 있습니다.

예상문제 10선

1. 일반 큐와 최소값을 높은 우선순위로 보는 우선순위 큐의 삭제 기준을 올바르게 비교한 것은?

① 둘 다 배열의 마지막 값을 먼저 삭제한다. ② 일반 큐는 최솟값을, 우선순위 큐는 먼저 들어온 값을 삭제한다. ③ 일반 큐는 먼저 들어온 값을, 우선순위 큐는 현재 최솟값을 삭제한다. ④ 일반 큐는 루트 값을, 우선순위 큐는 rear 값을 삭제한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 일반 큐의 삭제 위치는 front이며 마지막 위치가 아니다.
• ② 오답: 두 자료구조의 선택 기준을 서로 뒤바꾸었다.
• ③ 정답: 일반 큐는 도착 순서, 주어진 우선순위 큐는 작은 키를 처리 순서로 사용한다.
• ④ 오답: 루트는 힙 구현의 위치이며 우선순위 큐의 추상적인 삭제 기준 자체가 아니다.

2. 최소 힙이 되기 위한 조건으로 옳은 것은?

① 완전 이진 트리이며 모든 부모가 자신의 자식보다 작거나 같다. ② 완전 이진 트리이며 모든 왼쪽 자식이 오른쪽 자식보다 작다. ③ 루트가 최솟값이면 트리의 모양과 아래 간선은 상관없다. ④ 각 노드의 왼쪽 서브트리는 작고 오른쪽 서브트리는 커야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 완전성은 배열 저장 모양을, 부모≤자식은 최소 힙의 우선순위 관계를 보장한다.
• ② 오답: 형제 사이의 좌우 대소는 최소 힙의 성립 조건이 아니다.
• ③ 오답: 루트 아래의 한 간선이라도 부모가 자식보다 크면 최소 힙이 아니다.
• ④ 오답: 이는 이진 탐색 트리와 혼동한 설명이며 힙은 서브트리 전체의 좌우 정렬을 요구하지 않는다.

3. 배열 [2, 7, 5, 12, 4, 9]를 1번부터 저장한 최소 힙 후보가 실패하는 직접 원인은?

① 루트 2가 두 자식보다 작기 때문이다. ② 인덱스 3의 값 5가 인덱스 6의 값 9보다 작기 때문이다. ③ 마지막 레벨의 값 개수가 짝수가 아니기 때문이다. ④ 부모 7이 자식 4보다 커서 인덱스 2와 5의 관계가 깨지기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 루트가 자식보다 작은 것은 최소 힙에 맞지만 아래의 모든 간선을 보장하지 않는다.
• ② 오답: 부모 5와 자식 9의 관계는 5≤9이므로 정상이다.
• ③ 오답: 완전 이진 트리의 마지막 레벨은 왼쪽부터 채우면 홀수 개의 노드도 가질 수 있다.
• ④ 정답: 인덱스 5의 부모는 2이고 7≤4가 거짓이므로 최소 힙 조건을 위반한다.

4. 루트가 인덱스 1인 배열 힙에서 인덱스 6 노드의 부모와 두 자식 후보 인덱스는?

① 부모 2, 자식 7과 8 ② 부모 3, 자식 12와 13 ③ 부모 5, 자식 6과 7 ④ 부모 3, 자식 11과 12

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 부모를 i-4, 자식을 연속한 다음 칸처럼 계산해 힙 인덱스식을 적용하지 않았다.
• ② 정답: 정수 나눗셈 6/2=3, 왼쪽 2×6=12, 오른쪽 2×6+1=13이다.
• ③ 오답: 배열의 인접 인덱스가 트리의 부모·자식 관계를 뜻하지 않는다.
• ④ 오답: 부모는 맞지만 자식 식에서 현재 인덱스를 두 배 하지 않았다.

5. 최소 힙의 루트를 삭제한 뒤 마지막 값 temp를 내릴 때 반복할 판단은?

① 두 자식 중 큰 자식을 고르고 temp보다 크면 올린다. ② 왼쪽 자식만 골라 루트까지 위로 이동한다. ③ 부모와 형제를 비교해 더 큰 값을 말단으로 보낸다. ④ 실제 자식 중 작은 값을 고르고, temp가 더 크면 그 자식을 위로 올린다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 큰 자식을 올리면 그 아래에 더 작은 형제 자식이 남아 최소 힙 관계가 깨질 수 있다.
• ② 오답: 오른쪽 자식이 더 작을 수 있으며 삭제 복구 방향은 루트에서 아래쪽이다.
• ③ 오답: 비교 대상은 현재 빈자리의 자식들과 temp이며 형제와 부모를 함께 이동시키지 않는다.
• ④ 정답: 작은 자식을 먼저 올리고 temp가 그보다 작거나 같은 위치에서 멈춰야 최소 관계가 복구된다.

6. 최소 힙 [3, 8, 6, 14, 11, 9, 17]에서 루트 3을 삭제한 최종 배열은?

① [8, 6, 17, 14, 11, 9] ② [6, 8, 17, 14, 11, 9] ③ [6, 8, 9, 14, 11, 17] ④ [17, 8, 6, 14, 11, 9]

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 첫 단계에서 두 자식 8과 6 중 큰 8을 선택해 루트에 놓았다.
• ② 오답: 루트 선택은 맞지만 17 아래에 더 작은 자식 9를 남겨 인덱스 3의 관계가 깨진다.
• ③ 정답: 6과 9를 차례로 올린 뒤 마지막 값 17을 인덱스 6에 두면 모든 간선이 최소 관계를 만족한다.
• ④ 오답: 마지막 값을 루트에 둔 채 아래로 복구하지 않아 17이 자식 8과 6보다 크다.

7. 최소 힙에 새 값을 삽입하는 흐름으로 옳은 것은?

① 말단 후보 자리 생성 → 부모가 더 크면 부모를 아래로 복사 → 멈춘 자리에 새 값 저장 ② 루트 자리 생성 → 두 자식 중 큰 값을 선택 → 새 값을 말단에 저장 ③ 말단 값 삭제 → 작은 자식을 위로 이동 → 새 값을 루트에 저장 ④ 배열 전체 정렬 → 중간값 선택 → 오른쪽 빈칸에 새 값 저장

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 완전성을 위해 말단부터 시작하고 부모와의 최소 힙 관계가 맞는 위치까지 위로 이동한다.
• ② 오답: 루트에서 자식을 고르는 것은 삭제 복구 방향이며 삽입은 말단에서 시작한다.
• ③ 오답: 삽입하면서 기존 말단 값을 삭제하지 않고 새 값을 루트에 바로 확정하지도 않는다.
• ④ 오답: 힙은 배열 전체 정렬이나 중간값 선택을 삽입 조건으로 요구하지 않는다.

8. 최소 힙 [6, 8, 9, 14, 11, 17]에 5를 삽입할 때 값 5가 거치는 후보 인덱스는?

① 7 → 6 → 5 ② 7 → 3 → 1 ③ 1 → 2 → 4 ④ 7 → 4 → 2

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 부모 인덱스는 한 칸씩 감소하지 않고 정수 나눗셈 i/2로 구한다.
• ② 정답: 새 말단 7의 부모는 3, 다시 그 부모는 1이며 5가 9와 6보다 작아 루트까지 올라간다.
• ③ 오답: 이는 루트에서 자식 쪽으로 내려가는 방향으로 삽입의 시작점과 반대다.
• ④ 오답: 인덱스 7의 부모는 4가 아니라 정수 나눗셈으로 구한 3이다.

9. 최소 힙 삭제 코드에서 두 자식을 비교하기 전에 child < size를 확인하는 이유는?

① 왼쪽 자식의 값이 부모보다 작은지 미리 보장하기 위해서다. ② 배열의 0번 칸을 자식으로 사용하기 위해서다. ③ 마지막 값을 삭제하지 않고 크기를 유지하기 위해서다. ④ 오른쪽 자식 child+1이 실제 범위에 있을 때만 그 값을 읽기 위해서다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 이 조건은 값의 대소가 아니라 오른쪽 자식의 존재 여부를 검사한다.
• ② 오답: 강의 구현은 0번 칸을 비우고 루트를 1번에 둔다.
• ③ 오답: 루트 삭제에서는 마지막 값을 임시 보관한 뒤 크기를 이미 1 줄인다.
• ④ 정답: child==size이면 왼쪽 자식 하나만 존재하므로 child+1을 비교하면 범위를 벗어난다.

10. 배열 힙의 삭제·삽입 결과를 검산하는 순서로 가장 적절한 것은?

① 형제 정렬 확인 → 전체 배열 정렬 → 루트 위치 변경 → 크기 추정 ② 루트·크기 표시 → 완전성 확인 → 이동 방향과 비교 대상 추적 → 모든 부모·자식 관계 검산 ③ 최종 루트만 확인 → 나머지 값의 입력 순서 복원 → 빈칸을 임의로 채움 ④ 배열 0번을 루트로 변경 → 모든 값을 좌우 정렬 → 마지막 노드를 삭제

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 형제와 전체 배열의 정렬은 힙 조건이 아니며 크기는 연산에서 직접 갱신해야 한다.
• ② 정답: 배열 경계와 모양을 먼저 고정한 뒤 연산 경로를 추적하고 모든 간선을 확인하는 순서다.
• ③ 오답: 루트 하나만 맞아도 아래 간선이 깨질 수 있고 완전 이진 트리에 임의의 빈칸을 둘 수 없다.
• ④ 오답: 강의 구현의 루트 인덱스를 바꾸고 이진 탐색 트리식 좌우 정렬을 적용한 잘못된 절차다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 우선순위 큐와 힙의 관계, 배열 인덱스, 삭제·삽입 흐름을 학습 목적에 맞게 재구성한 비공식 학습자료입니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 자료구조 9강 「힙」 강의록(2023)
• 보충 자료: 외부 자료는 사용하지 않았으며 수치 추적 예제는 강의 범위 안에서 학습용으로 직접 구성했습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-18