[자료구조] Heap 구현하기

긍긍·2025년 5월 31일

TIL 자료구조 힙

공부기록

목록 보기

3/4

💡 힙(Heap)이란?

1. 모양 속성 (Shape Property)

완전 이진 트리 또는 거의 완전 이진 트리여야 함 → 노드들이 왼쪽부터 차례로 채워진 형태를 갖춤

2. 힙 정렬 속성 (Heap Ordering Property)

최대 힙 (max-heap): 부모 노드의 키 값이 자식 노드들의 키 값보다 크거나 같음 → 부모 우선 구조 (Parental Dominance)
최소 힙 (min-heap): 부모 노드의 키 값이 자식 노드들의 키 값보다 작음

✅ 힙의 특징

루트 노드는 항상 가장 큰 값(max-heap의 경우) 또는 가장 작은 값(min-heap의 경우)을 가짐
왼쪽과 오른쪽 서브트리도 각각 힙 구조를 유지함
힙은 일반적으로 배열(Array) 로 구현함 → 배열을 사용하면 자식 노드와 부모 노드의 인덱스를 수학적으로 쉽게 계산 가능
- 왼쪽 자식: 2 * i + 1
- 오른쪽 자식: 2 * i + 2
- 부모 노드: (i - 1) / 2

힙 구현하기

힙 구조체

typedef struct
{
	int	last;
	int	capacity;
	void **heapArr;
	int (*compare) (const void *, const void *);
} HEAP;

🤔힙 배열을 생성하는데 왜 이중포인터를 사용할까?

typedef struct
{
	int	last;
	int	capacity;
	void **heapArr;
	int (*compare) (const void *, const void *);
} HEAP;

🔸 1. 배열을 만들기 위한 포인터
✅ 목적: 동적 배열을 구현하기 위해

이중 포인터 void **heapArr는"포인터 배열"을 만들기 위해 쓰임

📌 예시:


void **heapArr = malloc(sizeof(void*) * capacity);

이렇게 하면 heapArr는 포인터들을 담는 배열

즉, 각 원소는 다시 데이터를 가리키는 포인터


heapArr
  ↓
+------+------+------+------+
| *    | *    | *    | ...  |  → 각각 void* 타입 (데이터 주소)
+------+------+------+------+

그래서:

heapArr[0] → 데이터 0의 주소 (예: int*, tWord*)
heapArr[1] → 데이터 1의 주소

🔸 2. 어떤 형태이든 올 수 있도록 하는 포인터

✅ 목적: 자료형에 관계없이 다양한 데이터를 저장하기 위해

void *는 "형태가 정해지지 않은 주소"를 저장할 수 있는 포인터

즉, 어떤 자료형이든 담을 수 있음:

int*, char*, float*, 구조체 포인터 등 다 가능
단, 사용 시에는 캐스팅이 필요

힙 생성


HEAP *heap_Create(int (*compare)(const void *, const void *)) {
    HEAP *heap = (HEAP *)malloc(sizeof(HEAP));
    if (!heap) return NULL;
    heap->heapArr = (void **)malloc(sizeof(void *) * INIT_CAPACITY);
    //메모리 할당 중간 실패 시 메모리 누수 방지
    if (!heap->heapArr) {
        free(heap);
        return NULL;
    }
    //현재 요소 없음 : last는 -1
    heap->last = -1;
    heap->capacity = INIT_CAPACITY;
    heap->compare = compare;
    return heap;
}

힙 구조를 그림으로 나타내면 아래와 같음
스크린샷 2025-05-31 오후 8.12.56.png

Destory


void heap_Destroy(HEAP *heap, void (*remove_data)(void *)) {
    for (int i = 0; i <= heap->last; i++) {
        remove_data(heap->heapArr[i]);
    }
    free(heap->heapArr);
    free(heap);
}

힙 삽입

//dataPtr : 삽입할 데이터의 주소
int heap_Insert(HEAP *heap, void *dataPtr) {
    if (heap->last + 1 >= heap->capacity) {
        //메모리 재할당 (현재 메모리의 2배)
        void **temp = realloc(heap->heapArr, sizeof(void *) * heap->capacity * 2);
        if (!temp) return 0;
        heap->heapArr = temp;
        heap->capacity *= 2;
    }
    //last 인덱스를 하나 증가시키고 새 데이터를 해당 위치에 삽입
    heap->last++;
    heap->heapArr[heap->last] = dataPtr;
    //새로 삽입된 요소가 heap 조건을 만족시키도록 위로 올리기 
    _reheapUp(heap, heap->last);
    //성공적으로 삽입되었으면 1 반환
    return 1;
}

삭제

힙은 루트 노트를 삭제하고 마지막 노드를 루트로 이동한다. 이후 reheapDown을 통해 힙 정렬을 한다.


int heap_Delete(HEAP *heap, void **dataOutPtr) {
    //힙이 비었는지 확인
    if (heap->last < 0) return 0;
    *dataOutPtr = heap->heapArr[0];
    //마지막 노드를 루트로 이동
    //이후에 last--로 힙 크기 감소
    heap->heapArr[0] = heap->heapArr[heap->last--];
    _reheapDown(heap, 0);
    return 1;
}