Heap

힙

• 모든 부분 트리에서 사용자 지정 조건을 만족하는 완전이진트리
  • 특정 조건 : 최댓값 / 최솟값 등등 여러가지 기준을 손수 만들 수 있음
  • 특정 조건을 우선순위라고 얘기하기도 함
• 데이터를 정렬하는 경우에 주로 사용 ( 우선순위 큐 )
  • 배열을 이용하여 구현하지만, 순서가 항상 정렬되어있는 것은 아님 ( 반정렬 )

최소 힙

구현 방법

1. 기본 구조

1. 배열을 사용하여 구현한다
2. 인덱스는 0이 아닌 1부터 사용한다
3. 자식과 부모의 인덱스 관계는 다음과 같다
   • 왼쪽 자식: $2 \times i$
   • 오른쪽 자식: $2 \times i + 1$
   • 부모: $i \div 2$
4. 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같아야 한다

2. 노드 삽입 과정

1. 새 노드를 힙의 가장 마지막 위치에 삽입한다
2. 부모 노드와 비교하여, 부모보다 크면 두 노드의 위치를 교환한다
3. 교환 후 부모 노드로 인덱스를 이동하여 위 과정을 반복한다
4. 더 이상 부모보다 크지 않거나 root(인덱스 1)에 도달하면 종료한다

$\Rightarrow$ 즉, 부모 ≥ 자식 조건을 만족할 때까지 위로 올라가며 재정렬한다

3. 노드 제거 과정

1. 루트 노드(최댓값) 을 반환한다
2. 힙의 마지막 노드를 루트로 이동시키고, 힙 크기를 1 줄인다
3. 루트 노드부터 자식 노드와 비교하며, 더 큰 자식과 교환한다
4. 부모 ≥ 자식 조건이 만족될 때까지 아래로 내려가며 반복한다

$\Rightarrow$ 즉, 힙의 우선순위를 유지하도록 아래로 내려가며 재정렬한다

소스코드

#include <stdio.h>

#define MAX_IDX 100

int min_heap[MAX_IDX + 1];
int heap_size = 0;

#define PARENT(x) ((x) / 2)
#define LEFT(x) ((x) * 2)
#define RIGHT(x) ((x) * 2 + 1)

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 원소 삽입
void insert(int x) {
    if (heap_size >= MAX_IDX) {
        printf("Heap is full!\n");
        return;
    }

    // 마지막 위치에 삽입
    heap_size++;
    min_heap[heap_size] = x;

    // 부모와 비교하면서 위로 올림 (heapify-up)
    int idx = heap_size;
    while (idx > 1 && min_heap[idx] < min_heap[PARENT(idx)]) {
        swap(&min_heap[idx], &min_heap[PARENT(idx)]);
        idx = PARENT(idx);
    }
}

// 최소값(루트) 제거 및 반환
int pop() {
    if (heap_size == 0) {
        printf("Heap is empty!\n");
        return -1;
    }

    int min_val = min_heap[1];
    min_heap[1] = min_heap[heap_size];
    heap_size--;

    // 자식들과 비교하며 아래로 내려감 (heapify-down)
    int idx = 1;
    while (LEFT(idx) <= heap_size) {
        int smaller = LEFT(idx);
        if (RIGHT(idx) <= heap_size && min_heap[RIGHT(idx)] < min_heap[smaller]) {
            smaller = RIGHT(idx);
        }

        if (min_heap[idx] <= min_heap[smaller])
            break;

        swap(&min_heap[idx], &min_heap[smaller]);
        idx = smaller;
    }

    return min_val;
}

void print_heap() {
    for (int i = 1; i <= heap_size; i++) {
        printf("%d ", min_heap[i]);
    }
    printf("\n");
}

int main() {
    insert(30);
    insert(10);
    insert(50);
    insert(20);
    insert(40);

    print_heap(); // 현재 heap 상태 출력

    printf("pop: %d\n", pop());
    print_heap();

    printf("pop: %d\n", pop());
    print_heap();

    return 0;
}

최대 힙

구현 방법

1. 기본 구조

1. 배열을 사용하여 구현한다
2. 인덱스는 1부터 사용한다
3. 자식과 부모의 인덱스 관계는 다음과 같다
   • 왼쪽 자식: $2 \times i$
   • 오른쪽 자식: $2 \times i + 1$
   • 부모: $i \div 2$
4. 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같아야 한다

2. 노드 삽입 과정

1. 새 노드를 힙의 가장 마지막 위치에 삽입한다
2. 부모 노드와 비교하여, 부모보다 작으면 두 노드의 위치를 교환한다
3. 교환 후 부모 노드로 인덱스를 이동하여 위 과정을 반복한다
4. 더 이상 부모보다 작지 않거나 root에 도달하면 종료한다

$\Rightarrow$ 즉, 부모 ≤ 자식 조건을 만족할 때까지 위로 올라가며 재정렬한다

3. 노드 제거 과정

1. 루트 노드(최솟값) 을 반환한다
2. 힙의 마지막 노드를 루트로 이동시키고, 힙 크기를 1 줄인다
3. 루트 노드부터 자식 노드와 비교하며, 더 작은 자식과 교환한다
4. 부모 ≤ 자식 조건이 만족될 때까지 아래로 내려가며 반복한다

$\Rightarrow$ 즉, 힙의 우선순위를 유지하도록 아래로 내려가며 재정렬한다

소스 코드

#include <stdio.h>

#define MAX_IDX 100

int max_heap[MAX_IDX + 1];
int heap_size = 0;

#define PARENT(x) ((x) / 2)
#define LEFT(x) ((x) * 2)
#define RIGHT(x) ((x) * 2 + 1)

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 삽입 함수
void insert(int x) {
    if (heap_size >= MAX_IDX) {
        printf("Heap is full!\n");
        return;
    }

    // 새 원소를 마지막 위치에 추가
    heap_size++;
    max_heap[heap_size] = x;

    // 부모와 비교하며 위로 올림 (heapify-up)
    int idx = heap_size;
    while (idx > 1 && max_heap[idx] > max_heap[PARENT(idx)]) {
        swap(&max_heap[idx], &max_heap[PARENT(idx)]);
        idx = PARENT(idx);
    }
}

// 최댓값(루트) 제거 후 반환
int pop() {
    if (heap_size == 0) {
        printf("Heap is empty!\n");
        return -1;
    }

    int max_val = max_heap[1]; // 루트 노드 값
    max_heap[1] = max_heap[heap_size]; // 마지막 원소를 루트로 이동
    heap_size--;

    // 아래로 내려가며 재정렬 (heapify-down)
    int idx = 1;
    while (LEFT(idx) <= heap_size) {
        int larger = LEFT(idx);
        if (RIGHT(idx) <= heap_size && max_heap[RIGHT(idx)] > max_heap[larger]) {
            larger = RIGHT(idx);
        }

        if (max_heap[idx] >= max_heap[larger])
            break;

        swap(&max_heap[idx], &max_heap[larger]);
        idx = larger;
    }

    return max_val;
}

void print_heap() {
    for (int i = 1; i <= heap_size; i++) {
        printf("%d ", max_heap[i]);
    }
    printf("\n");
}

int main() {
    insert(10);
    insert(40);
    insert(30);
    insert(20);
    insert(50);

    print_heap();

    printf("pop: %d\n", pop());
    print_heap();

    printf("pop: %d\n", pop());
    print_heap();

    return 0;
}