Min-Heap (lib/min_heap)

리눅스 커널의 범용 최소 힙(min-heap) 자료구조를 심층 분석합니다. include/linux/min_heap.h에 정의된 DEFINE_MIN_HEAP 매크로(Macro), min_heap_callbacks 비교자 패턴, push/pop/peek/heapify API의 내부 구현을 추적하고, sift-up과 sift-down 알고리즘의 단계별 동작을 시각화합니다. perf_event 멀티플렉싱, hrtimer 타이머(Timer) 큐, SCHED_DEADLINE EDF 스케줄링, CFS 대역폭(Bandwidth) 제어 등 커널 서브시스템에서의 실전 활용 사례와 rbtree 대비 장단점 비교까지 포괄합니다.

힙 속성 (Min-Heap Property)

최소 힙(min-heap)은 완전 이진 트리(complete binary tree)에 힙 순서 속성(heap-order property)을 결합한 자료구조입니다. 두 가지 불변식이 동시에 성립합니다.

형태 속성 (Shape Property)

트리는 항상 완전 이진 트리입니다. 마지막 레벨을 제외한 모든 레벨이 가득 차 있고, 마지막 레벨의 노드는 왼쪽부터 채워집니다. 이 속성 덕분에 배열로 표현할 때 빈 공간이 발생하지 않습니다.

순서 속성 (Heap-Order Property)

모든 노드 i에 대해 heap[parent(i)] ≤ heap[i]가 성립합니다. 즉 부모 노드의 값은 항상 자식 노드의 값 이하입니다. 이 불변식에 의해 루트 노드(data[0])는 항상 전체 힙의 최솟값입니다.

힙 속성이 깨지는 경우는 두 가지뿐입니다. (1) 새 원소가 부모보다 작을 때(push 후) → sift-up으로 복원, (2) 루트가 자식보다 클 때(pop 후) → sift-down으로 복원. 모든 연산은 이 두 가지 복원 경로 중 하나를 사용합니다.

배열 기반 트리 표현

완전 이진 트리는 배열의 인덱스만으로 부모-자식 관계를 표현할 수 있습니다. 포인터가 필요 없어 메모리 오버헤드(Overhead)가 없고, 연속 메모리 배치로 캐시 성능이 우수합니다.

인덱스 공식

이 공식들은 비트 연산으로 최적화됩니다. (i - 1) >> 1은 부모 인덱스, (i << 1) | 1은 왼쪽 자식, (i << 1) + 2는 오른쪽 자식입니다. 커널의 min_heap 구현은 이 산술을 직접 사용합니다.

min_heap 구조체

커널의 min-heap은 제네릭 매크로 기반으로 구현됩니다. DEFINE_MIN_HEAP 매크로가 타입별 힙 구조체를 생성하고, 공통 API가 void *와 원소 크기를 통해 동작합니다.

/* include/linux/min_heap.h */

#define DEFINE_MIN_HEAP(type, name)   \
struct name {                           \
    int nr;                              \
    int size;                            \
    type *data;                          \
    type preallocated[];                 \
}

/* 프리할당 없는 기본 힙 */
typedef DEFINE_MIN_HEAP(void, min_heap) min_heap_t;

/* 프리할당 원소를 포함하는 정적 힙 */
#define DEFINE_MIN_HEAP_STATIC(type, name, count) \
struct name {                                     \
    int nr;                                        \
    int size;                                      \
    type *data;                                    \
    type preallocated[count];                      \
}

초기화 패턴

/* 정적 프리할당 힙 (스택에 선언) */
DEFINE_MIN_HEAP_STATIC(u64, timer_heap, 16);
struct timer_heap heap = {
    .nr   = 0,
    .size = 16,
    .data = heap.preallocated,
};

/* 동적 할당 힙 */
DEFINE_MIN_HEAP(u64, event_heap);
struct event_heap heap;
heap.nr   = 0;
heap.size = max_events;
heap.data = kmalloc_array(max_events, sizeof(u64), GFP_KERNEL);

min_heap_callbacks: 비교자와 스왑(Swap)

min-heap의 동작은 비교 함수와 스왑 함수 두 콜백에 의해 결정됩니다. 이를 통해 동일한 힙 코드가 임의의 타입에 대해 동작합니다.

/* include/linux/min_heap.h */
struct min_heap_callbacks {
    bool (*less)(const void *lhs, const void *rhs, void *args);
    void (*swp)(void *lhs, void *rhs, void *args);
};

콜백 구현 예시

/* 정수 비교: 가장 단순한 형태 */
static bool u64_less(const void *lhs, const void *rhs, void *args)
{
    return *(const u64 *)lhs < *(const u64 *)rhs;
}

/* 구조체 비교: 특정 필드를 키로 사용 */
static bool event_less(const void *lhs, const void *rhs, void *args)
{
    const struct perf_event *a = *((const struct perf_event **)lhs);
    const struct perf_event *b = *((const struct perf_event **)rhs);
    return a->weight < b->weight;
}

/* 커스텀 스왑: 인덱스 역추적이 필요한 경우 */
static void event_swp(void *lhs, void *rhs, void *args)
{
    struct perf_event **a = lhs, **b = rhs;
    swap(*a, *b);
    /* 스왑 후 인덱스 갱신 */
    (*a)->heap_index = a - (struct perf_event **)args;
    (*b)->heap_index = b - (struct perf_event **)args;
}

static const struct min_heap_callbacks event_callbacks = {
    .less = event_less,
    .swp  = event_swp,
};

push 연산 (삽입)

min_heap_push()는 새 원소를 힙에 삽입합니다. 배열의 마지막 위치에 원소를 추가한 후, sift-up 연산으로 힙 속성을 복원합니다.

알고리즘

1. heap->nr이 heap->size와 같으면 실패 (힙이 가득 참) — -ENOMEM에 해당하는 에러 경로
2. 새 원소를 data[nr] 위치에 복사
3. nr++
4. 삽입 위치(nr - 1)에서 sift-up 시작: 부모와 비교하여 새 원소가 더 작으면 교환, 루트에 도달하거나 부모 이상이면 중단

/* include/linux/min_heap.h — 단순화된 push 구현 */
static inline int min_heap_push(min_heap_t *heap,
        const void *element, size_t elem_size,
        const struct min_heap_callbacks *func, void *args)
{
    void *data = heap->data;
    int pos;

    if (heap->nr >= heap->size)
        return -1;  /* 힙 가득 참 */

    /* 배열 끝에 삽입 */
    pos = heap->nr++;
    memcpy(data + pos * elem_size, element, elem_size);

    /* sift-up: 부모보다 작으면 교환하며 올라감 */
    min_heap_sift_up(heap, elem_size, func, args, pos);

    return 0;
}

sift-up 상세

/* sift-up: 새 원소를 올바른 위치로 올림 */
static inline void min_heap_sift_up(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func,
        void *args, int pos)
{
    void *data = heap->data;
    int parent;

    while (pos > 0) {
        parent = (pos - 1) / 2;
        if (!func->less(data + pos * elem_size,
                        data + parent * elem_size, args))
            break;  /* 부모 이하 → 힙 속성 만족 */
        func->swp(data + pos * elem_size,
                  data + parent * elem_size, args);
        pos = parent;
    }
}

pop 연산 (최솟값 제거)

min_heap_pop()는 힙에서 최솟값(루트)을 제거합니다. 마지막 원소를 루트로 이동시킨 후, sift-down 연산으로 힙 속성을 복원합니다.

알고리즘

1. heap->nr이 0이면 힙이 비어 있음
2. data[0](루트)과 data[nr - 1](마지막 원소)을 교환
3. nr-- (마지막 위치의 원래 루트를 논리적으로 제거)
4. 루트 위치(0)에서 sift-down 시작: 자식 중 더 작은 것과 비교, 자식보다 크면 교환, 리프에 도달하거나 자식 이하이면 중단

/* include/linux/min_heap.h — 단순화된 pop 구현 */
static inline void min_heap_pop(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func, void *args)
{
    if (heap->nr <= 0)
        return;

    /* 루트와 마지막 원소 교환 */
    heap->nr--;
    if (func->swp)
        func->swp(heap->data,
                  heap->data + heap->nr * elem_size, args);
    else
        __min_heap_swap(heap->data,
                        heap->data + heap->nr * elem_size,
                        elem_size);

    /* 루트에서 sift-down */
    min_heap_sift_down(heap, elem_size, func, args, 0);
}

sift-down 상세

/* sift-down: 루트를 올바른 위치로 내림 */
static inline void min_heap_sift_down(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func,
        void *args, int pos)
{
    void *data = heap->data;
    int left, right, smallest;

    while (1) {
        left     = 2 * pos + 1;
        right    = 2 * pos + 2;
        smallest = pos;

        if (left < heap->nr &&
            func->less(data + left * elem_size,
                       data + smallest * elem_size, args))
            smallest = left;

        if (right < heap->nr &&
            func->less(data + right * elem_size,
                       data + smallest * elem_size, args))
            smallest = right;

        if (smallest == pos)
            break;  /* 힙 속성 만족 */

        func->swp(data + pos * elem_size,
                  data + smallest * elem_size, args);
        pos = smallest;
    }
}

peek 연산: O(1) 최솟값 조회

min_heap_peek()는 힙에서 최솟값을 제거하지 않고 조회만 합니다. 힙 속성에 의해 최솟값은 항상 data[0]에 있으므로, 단순히 첫 번째 원소의 포인터를 반환합니다.

/* include/linux/min_heap.h */
static inline void *min_heap_peek(min_heap_t *heap)
{
    return heap->nr ? heap->data : NULL;
}

/* 안전한 peek 패턴 */
const u64 *p = min_heap_peek(&heap);
if (p) {
    u64 min_val = *p;  /* 즉시 복사 */
    /* 이후 min_val 사용 */
}

/* 위험한 패턴: pop 후 이전 peek 포인터 사용 */
const u64 *p = min_heap_peek(&heap);
min_heap_pop(&heap, ...);
/* p가 가리키는 값이 변경됨 — 버그! */

heapify: O(n) 배열→힙 변환

min_heapify_all()은 임의 순서의 배열을 유효한 힙으로 변환합니다. 개별 push를 n번 반복하면 O(n log n)이지만, heapify는 역순 sift-down으로 O(n) 시간에 완료됩니다.

알고리즘

/* include/linux/min_heap.h — heapify 구현 */
static inline void min_heapify_all(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func, void *args)
{
    int i;

    /* 마지막 비-리프 노드부터 역순으로 sift-down
     * 리프 노드(인덱스 nr/2 ~ nr-1)는 이미 유효한 힙 */
    for (i = heap->nr / 2 - 1; i >= 0; i--)
        min_heap_sift_down(heap, elem_size, func, args, i);
}

O(n) 시간 복잡도 증명

직관적으로 O(n log n)처럼 보이지만, 각 레벨에서의 sift-down 비용이 다릅니다.

총 비용은 ∑_k=1^{log n} kn/2^k+1 = n ⋅ ∑_k=1^∞ k/2^k+1 = n ⋅ 1 = O(n)입니다. 핵심 통찰은 노드가 가장 많은 하위 레벨의 sift-down 깊이가 가장 짧다는 것입니다.

임의 원소 삭제

min_heap_del()은 인덱스로 지정된 임의 위치의 원소를 힙에서 제거합니다. pop이 항상 루트(인덱스 0)를 제거하는 것과 달리, 임의 인덱스 삭제는 sift-up 또는 sift-down이 모두 필요할 수 있습니다.

알고리즘

1. 삭제할 인덱스 i의 원소를 마지막 원소(data[nr-1])로 교체
2. nr--
3. 교체된 원소가 부모보다 작으면 sift-up, 자식보다 크면 sift-down

/* include/linux/min_heap.h — 임의 삭제 */
static inline void min_heap_del(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func,
        void *args, int pos)
{
    void *data = heap->data;

    if (pos >= heap->nr)
        return;

    /* 마지막 원소와 교환 */
    heap->nr--;
    if (pos != heap->nr) {
        if (func->swp)
            func->swp(data + pos * elem_size,
                      data + heap->nr * elem_size, args);
        else
            __min_heap_swap(data + pos * elem_size,
                            data + heap->nr * elem_size,
                            elem_size);

        /* 교체된 값에 따라 sift-up 또는 sift-down */
        if (pos > 0 && func->less(data + pos * elem_size,
                data + ((pos - 1) / 2) * elem_size, args))
            min_heap_sift_up(heap, elem_size, func, args, pos);
        else
            min_heap_sift_down(heap, elem_size, func, args, pos);
    }
}

API 레퍼런스

include/linux/min_heap.h에 정의된 전체 API를 정리합니다. 모든 함수는 static inline으로 헤더에서 인라인 확장됩니다.

헬퍼 매크로

/* 힙 상태 검사 */
static inline bool min_heap_full(min_heap_t *heap)
{
    return heap->nr >= heap->size;
}

static inline bool min_heap_empty(min_heap_t *heap)
{
    return heap->nr == 0;
}

/* 타입 안전 래퍼 매크로 (v6.5+) */
#define __min_heap_cast(_heap)    \
    (min_heap_t *)(void *)(_heap)

#define __min_heap_elem_size(_heap)   \
    sizeof(*(_heap)->data)

perf_event 스케줄링

perf 서브시스템은 min-heap의 가장 대표적인 커널 내 사용자입니다. 하드웨어 PMU(Performance Monitoring Unit)의 카운터 수는 제한적이므로, 다수의 perf_event를 멀티플렉싱(time-sharing)해야 합니다. min-heap은 가장 짧은 타임슬라이스(Time Slice)를 가진 이벤트를 O(1)로 찾는 데 사용됩니다.

멀티플렉싱 메커니즘

PMU에 동시에 장착할 수 있는 이벤트 수가 n_hw개이고, 사용자가 요청한 이벤트가 n_req개일 때 n_req > n_hw이면 멀티플렉싱이 필요합니다. 각 이벤트에 가중치(weight)를 부여하고, min-heap으로 가장 적게 실행된 이벤트를 빠르게 선택합니다.

/* kernel/events/core.c — perf_event 멀티플렉싱 관련 */

/* 이벤트 힙 비교: 더 적게 실행된 이벤트가 우선 */
static bool perf_event_less(const void *lhs,
                             const void *rhs, void *args)
{
    struct perf_event *a = *(struct perf_event **)lhs;
    struct perf_event *b = *(struct perf_event **)rhs;

    /* 타임슬라이스가 짧은(덜 실행된) 이벤트가 우선 */
    return a->tstamp_running < b->tstamp_running;
}

/* rotation 시 힙에서 다음 이벤트 선택 */
static void perf_rotate_context(struct perf_cpu_context *cpuctx)
{
    struct perf_event **min_event;

    min_event = min_heap_peek(&cpuctx->heap);
    if (min_event) {
        /* 가장 적게 실행된 이벤트를 PMU에 장착 */
        perf_event_enable(*min_event);
        min_heap_pop(&cpuctx->heap, ...);
    }
}

hrtimer 통합

고해상도 타이머(hrtimer) 서브시스템은 나노초 정밀도의 타이머를 관리합니다. 여러 타이머 중 가장 빠른 만료 시간을 찾는 것이 핵심 연산이며, 이는 min-heap의 peek()에 해당합니다.

hrtimer에서의 힙 활용

hrtimer는 전통적으로 rbtree를 사용했지만, 최근 커널에서는 특정 경로에서 min-heap 패턴을 활용합니다. 만료 시간이 가장 이른 타이머가 항상 루트에 있으므로, 다음 인터럽트(Interrupt) 프로그래밍에 필요한 시간을 O(1)로 결정합니다.

/* hrtimer 만료 시간 비교 */
static bool timer_less(const void *lhs,
                       const void *rhs, void *args)
{
    const struct hrtimer *a = *((const struct hrtimer **)lhs);
    const struct hrtimer *b = *((const struct hrtimer **)rhs);

    /* ktime_t 비교: 더 이른 만료 시간이 우선 */
    return ktime_before(a->_softexpires, b->_softexpires);
}

/* 다음 인터럽트 시간 결정 */
ktime_t hrtimer_get_next_event(void)
{
    struct hrtimer **next = min_heap_peek(&timer_heap);
    if (next)
        return (*next)->_softexpires;
    return KTIME_MAX;
}

SCHED_DEADLINE (EDF) 스케줄러(Scheduler)

Earliest Deadline First (EDF) 스케줄링 정책을 구현하는 SCHED_DEADLINE 클래스는 각 태스크(Task)의 절대 데드라인을 기준으로 스케줄링합니다. 데드라인이 가장 이른 태스크를 빠르게 선택하는 것이 핵심이며, 이는 min-heap의 전형적인 사용 사례입니다.

dl_rq에서의 데드라인 관리

dl_rq(deadline run queue)는 rb_root_cached를 사용하여 rbtree의 leftmost 캐시로 O(1) 최솟값 접근을 제공합니다. 이 패턴은 사실상 rbtree 위에 min-heap의 peek() 의미론을 구현한 것입니다.

/* kernel/sched/deadline.c */
struct dl_rq {
    struct rb_root_cached root;  /* leftmost 캐시 포함 */
    u64   earliest_dl;            /* 캐시된 최소 데드라인 */
};

/* 가장 이른 데드라인 태스크 선택 */
static struct sched_dl_entity *pick_earliest_dl_entity(
        struct dl_rq *dl_rq)
{
    struct rb_node *left = rb_first_cached(&dl_rq->root);
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_dl_entity, rb_node);
}

CFS 대역폭 제어

CFS(Completely Fair Scheduler)의 대역폭 제어(bandwidth throttling)는 cgroup별 CPU 사용량을 제한합니다. 스로틀(throttle) 타이머의 관리에서 가장 이른 만료 시간을 추적하는 데 min-heap 패턴이 적용됩니다.

/* kernel/sched/fair.c — CFS 대역폭 관련 */
struct cfs_bandwidth {
    ktime_t           period;
    u64               quota;
    u64               runtime;
    struct hrtimer    period_timer;
    struct hrtimer    slack_timer;
    /* ... */
};

/* 스로틀된 cgroup 중 가장 빨리 해제될 것을 찾기 위해
 * 타이머 힙에서 peek()로 다음 unthrottle 시점 결정 */
static void do_sched_cfs_period_timer(
        struct cfs_bandwidth *cfs_b)
{
    /* 만료된 타이머 처리 후 다음 타이머 프로그래밍 */
    hrtimer_forward_now(&cfs_b->period_timer,
                        cfs_b->period);
}

메모리 레이아웃 분석

min-heap의 메모리 효율은 배열 기반 구조에서 비롯됩니다. 포인터 오버헤드 없이 원소만 연속 배치되므로, 같은 개수의 원소를 저장할 때 rbtree나 linked list보다 메모리 사용량이 적습니다.

인라인 vs 동적 할당

캐시 라인 정렬

/* 캐시 라인 정렬된 힙 선언 */
struct aligned_heap {
    DEFINE_MIN_HEAP_STATIC(u64, heap_data, 64);
} __aligned(L1_CACHE_BYTES);

/* per-CPU 힙: 각 CPU의 L1 캐시에 고정 */
static DEFINE_PER_CPU(struct aligned_heap, cpu_heap);

복잡도 분석

min-heap의 시간/공간 복잡도를 정리하고, 다른 우선순위(Priority) 큐 구현과 비교합니다.

시간 복잡도

공간 복잡도

rbtree vs min-heap 비교

커널에서 우선순위 기반 자료구조를 선택할 때 rbtree와 min-heap은 가장 대표적인 후보입니다. 각각의 강점과 약점을 체계적으로 비교합니다.

마이크로벤치마크 경향

구현 패턴

min-heap을 커널 코드에서 사용할 때의 타입 안전성, 인라인 최적화, 비교자 커스터마이징 패턴을 정리합니다.

타입 안전 래퍼 패턴

/* 타입 안전한 힙 정의 */
struct timer_entry {
    u64  expires;
    void (*callback)(void *);
    void *data;
};

/* 전용 힙 타입 선언 */
DEFINE_MIN_HEAP_STATIC(struct timer_entry, timer_heap_t, 32);

/* 타입 안전 API 래퍼 */
static inline int timer_heap_push(struct timer_heap_t *heap,
        const struct timer_entry *entry)
{
    return min_heap_push(
        __min_heap_cast(heap),
        entry,
        sizeof(*entry),
        &timer_callbacks,
        NULL);
}

static inline struct timer_entry *timer_heap_peek(
        struct timer_heap_t *heap)
{
    return (struct timer_entry *)min_heap_peek(
        __min_heap_cast(heap));
}

인라인 최적화

min-heap API는 모두 static inline이므로, 비교자와 스왑 함수도 static inline으로 정의하면 컴파일러가 전체 경로를 단일 함수로 인라인 확장합니다.

/* 컴파일러가 인라인 확장하는 전체 경로:
 *
 * min_heap_push()
 *   └─ min_heap_sift_up()
 *        └─ less()        ← 인라인
 *        └─ swp()         ← 인라인 (또는 memcpy)
 *
 * 결과: 함수 호출 0회, 루프와 비교/교환만 남음
 */

/* GCC __attribute__((always_inline))으로 강제 인라인 */
static __always_inline bool my_less(const void *a,
        const void *b, void *args)
{
    return *(const u64 *)a < *(const u64 *)b;
}

복합 키 비교

/* 2차 정렬 키를 사용하는 비교자 */
static bool task_deadline_less(const void *lhs,
                                const void *rhs, void *args)
{
    const struct task_entry *a = lhs;
    const struct task_entry *b = rhs;

    /* 1차 키: 데드라인 */
    if (a->deadline != b->deadline)
        return a->deadline < b->deadline;

    /* 2차 키: 우선순위 (동률 시) */
    return a->priority < b->priority;
}

디버깅(Debugging)

min-heap 관련 버그는 주로 힙 불변식 위반, 경계 조건 오류, 비교자 논리 오류에서 발생합니다.

힙 불변식 검증

/* 디버그 빌드용 힙 불변식 검증 함수 */
static void min_heap_verify(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func, void *args)
{
    int i;

    for (i = 1; i < heap->nr; i++) {
        int parent = (i - 1) / 2;
        if (func->less(heap->data + i * elem_size,
                       heap->data + parent * elem_size, args)) {
            WARN(1, "min_heap invariant violated: "
                 "data[%d] < data[%d] (parent)\n",
                 i, parent);
        }
    }
    WARN_ON(heap->nr < 0 || heap->nr > heap->size);
}

일반적 버그 패턴

ftrace를 활용한 추적

# min_heap_push/pop 호출 추적
echo 1 > /sys/kernel/debug/tracing/events/enable
echo 'p:push_probe min_heap_push' > /sys/kernel/debug/tracing/kprobe_events
echo 1 > /sys/kernel/debug/tracing/events/kprobes/push_probe/enable
cat /sys/kernel/debug/tracing/trace_pipe

/* 힙 상태 덤프 함수 */
static void min_heap_dump(min_heap_t *heap, size_t elem_size)
{
    int i;
    pr_info("min_heap: nr=%d size=%d\n", heap->nr, heap->size);
    for (i = 0; i < heap->nr; i++) {
        u64 *val = heap->data + i * elem_size;
        pr_info("  [%d] = %llu (parent=%d)\n",
                i, *val, i ? (i - 1) / 2 : -1);
    }
}

관련 커널 설정

min-heap 자체는 별도 CONFIG 옵션 없이 항상 사용 가능하지만, 관련 서브시스템과 디버깅 도구의 설정을 정리합니다.

발전 역사

리눅스 커널의 min-heap 구현은 여러 서브시스템에서 독립적으로 구현되던 힙 코드를 통합 라이브러리로 정리한 결과입니다.

고급 사용 패턴

decrease-key 연산

min-heap의 decrease-key는 특정 원소의 키를 감소시킨 후 힙 속성을 복원합니다. Dijkstra 알고리즘 등에서 핵심적으로 사용되며, 커널에서는 타이머 재설정에 해당합니다.

/* decrease-key 패턴: 키 감소 후 sift-up */
static void min_heap_decrease_key(min_heap_t *heap,
        size_t elem_size,
        const struct min_heap_callbacks *func,
        void *args, int pos, const void *new_val)
{
    /* 새 값이 현재 값보다 작은지 확인 */
    BUG_ON(!func->less(new_val,
            heap->data + pos * elem_size, args));

    /* 값 갱신 */
    memcpy(heap->data + pos * elem_size, new_val, elem_size);

    /* 키가 감소했으므로 sift-up만 필요 */
    min_heap_sift_up(heap, elem_size, func, args, pos);
}

Heap Sort 패턴

/* 힙 정렬: heapify 후 반복 pop */
static void heap_sort(void *data, int n, size_t elem_size,
        const struct min_heap_callbacks *func, void *args)
{
    min_heap_t heap = {
        .data = data,
        .nr   = n,
        .size = n,
    };

    /* O(n) 힙 구축 */
    min_heapify_all(&heap, elem_size, func, args);

    /* O(n log n) 정렬: 반복적으로 최솟값 추출 */
    while (heap.nr > 1)
        min_heap_pop(&heap, elem_size, func, args);

    /* 결과: data[]가 내림차순 정렬됨
     * (min-heap pop은 끝에서부터 채우므로) */
}

k-way 병합

/* k개의 정렬된 스트림을 병합하는 패턴 */
struct merge_entry {
    u64 value;      /* 현재 값 */
    int stream_id;  /* 출처 스트림 */
    int index;      /* 스트림 내 위치 */
};

/* k-way merge: 각 스트림의 현재 최솟값을 힙에 유지
 * peek() → 전체 최솟값, pop() → 해당 스트림에서 다음 값 push */

테스트

커널은 lib/test_min_heap.c에 min-heap 자체 테스트를 포함합니다. KUnit 프레임워크 기반으로 push/pop/heapify/delete의 정확성을 검증합니다.

# min-heap 테스트 모듈 빌드 및 실행
make -C /lib/modules/$(uname -r)/build M=lib \
    CONFIG_TEST_MIN_HEAP=m modules
insmod lib/test_min_heap.ko
dmesg | tail -20

# KUnit으로 실행 (v6.0+)
./tools/testing/kunit/kunit.py run min_heap

테스트 케이스

대안 자료구조

min-heap 외에 커널에서 사용되는 우선순위 기반 자료구조를 비교합니다.

* 인덱스 추적 필요 | ** rb_root_cached 사용 시 | *** 노드 포인터 보유 시 | † 슬롯 그라뉼래리티

동시성 고려사항

min-heap은 내부적으로 어떤 동기화 메커니즘도 제공하지 않습니다. 멀티코어 환경에서는 호출자가 반드시 적절한 락으로 보호해야 합니다.

락 선택 가이드

/* 인터럽트 안전한 힙 접근 패턴 */
struct safe_heap {
    spinlock_t lock;
    DEFINE_MIN_HEAP_STATIC(u64, heap, 64);
};

static void safe_push(struct safe_heap *sh, u64 val)
{
    unsigned long flags;

    spin_lock_irqsave(&sh->lock, flags);
    min_heap_push(__min_heap_cast(&sh->heap),
                  &val, sizeof(val), &callbacks, NULL);
    spin_unlock_irqrestore(&sh->lock, flags);
}

static bool safe_pop(struct safe_heap *sh, u64 *out)
{
    unsigned long flags;
    u64 *p;

    spin_lock_irqsave(&sh->lock, flags);
    p = min_heap_peek(__min_heap_cast(&sh->heap));
    if (p) {
        *out = *p;
        min_heap_pop(__min_heap_cast(&sh->heap),
                     sizeof(*p), &callbacks, NULL);
    }
    spin_unlock_irqrestore(&sh->lock, flags);

    return p != NULL;
}

락 없는 peek 최적화

특수한 경우, peek만 수행하는 읽기 경로는 READ_ONCE()로 보호할 수 있습니다. 단, 이는 원소가 원자적(Atomic)으로 읽을 수 있는 크기(8바이트 이하)이고, 힙 자체의 불변식 위반이 허용되는 경우에만 가능합니다.

/* 락 없는 대략적 최솟값 조회 (근사적 결과 허용 시) */
static u64 approx_min(struct safe_heap *sh)
{
    int nr = READ_ONCE(sh->heap.nr);
    if (nr > 0)
        return READ_ONCE(sh->heap.data[0]);
    return U64_MAX;
}
/* 주의: 반환값은 실제 최솟값과 다를 수 있음
 * heuristic/hint 용도로만 사용 */

실전 코드 사례

커널 소스에서 min-heap이 실제로 사용되는 대표적인 코드 경로를 분석합니다.

perf_event_context의 힙

/* kernel/events/core.c */
struct perf_event_context {
    /* ... */
    struct min_heap_struct {
        int nr;
        int size;
        struct perf_event **data;
        struct perf_event *preallocated[0];
    } heap;
    /* ... */
};

/* 컨텍스트 생성 시 힙 초기화 */
static void perf_event_ctx_init(struct perf_event_context *ctx,
                                 int max_events)
{
    ctx->heap.nr   = 0;
    ctx->heap.size = max_events;
    ctx->heap.data = kmalloc_array(max_events,
            sizeof(struct perf_event *), GFP_KERNEL);
}

bcache의 힙

블록 캐시 서브시스템 bcache는 가비지 컬렉션에서 가장 오래된 버킷을 추적하는 데 자체 힙 구현을 사용합니다. 이는 커널 범용 min_heap API 도입 이전에 작성되어 독자적인 매크로를 유지합니다.

/* drivers/md/bcache/bset.h — bcache 자체 힙 */
#define heap_peek(h)    ((h)->data[0])
#define heap_full(h)    ((h)->used == (h)->size)

/* GC 대상 선택: 가장 적게 사용된 버킷 */
static void invalidate_buckets_lru(struct cache *ca)
{
    while (!heap_empty(&ca->heap)) {
        struct bucket *b = heap_peek(&ca->heap);
        /* 가장 오래된 버킷 무효화 */
        heap_pop(&ca->heap, ...);
        __bch_invalidate_one_bucket(ca, b);
    }
}

thermal 서브시스템의 정렬

thermal 서브시스템에서 쿨링 디바이스 선택 시, 제한된 수의 후보 중 가장 효율적인 것을 선택하는 패턴에서 min-heap 방식의 비교가 활용됩니다.

이벤트 폴링(Polling) 시나리오

다중 소스에서 이벤트를 수집하고 타임스탬프 순서로 처리해야 하는 시나리오에서 min-heap은 자연스러운 선택입니다.

/* 다중 소스 이벤트 정렬 처리 */
struct event {
    u64  timestamp;
    u32  source_id;
    u32  type;
    void *payload;
};

static bool event_ts_less(const void *a, const void *b,
                          void *args)
{
    return ((const struct event *)a)->timestamp <
           ((const struct event *)b)->timestamp;
}

/* 각 소스에서 이벤트를 읽어 힙에 삽입
 * → peek()로 전역 최소 타임스탬프 결정
 * → pop() 후 해당 소스에서 다음 이벤트 push */
static void process_events_ordered(struct event_source *sources,
                                   int n_sources)
{
    DEFINE_MIN_HEAP_STATIC(struct event, ev_heap, 64);
    struct ev_heap heap = { .nr = 0, .size = 64,
                           .data = heap.preallocated };
    const struct min_heap_callbacks cbs = { .less = event_ts_less };
    int i;

    /* 각 소스의 첫 이벤트를 힙에 push */
    for (i = 0; i < n_sources; i++) {
        struct event e;
        if (source_read(&sources[i], &e) == 0)
            min_heap_push(__min_heap_cast(&heap),
                          &e, sizeof(e), &cbs, NULL);
    }

    /* 타임스탬프 순서로 처리 */
    while (heap.nr > 0) {
        struct event *min = min_heap_peek(
            __min_heap_cast(&heap));
        handle_event(min);

        int src = min->source_id;
        min_heap_pop(__min_heap_cast(&heap),
                     sizeof(struct event), &cbs, NULL);

        /* 해당 소스에서 다음 이벤트 push */
        struct event next;
        if (source_read(&sources[src], &next) == 0)
            min_heap_push(__min_heap_cast(&heap),
                          &next, sizeof(next), &cbs, NULL);
    }
}

성능 튜닝

min-heap의 성능을 극대화하기 위한 튜닝 포인트를 정리합니다.

원소 크기 최적화

sift-up/sift-down 과정에서 원소를 교환(swap)할 때 memcpy가 사용됩니다. 원소 크기가 크면 교환 비용이 증가하므로, 큰 구조체를 직접 저장하는 대신 포인터를 저장하는 것이 일반적입니다.

/* 포인터 힙: 큰 구조체에 적합 */
DEFINE_MIN_HEAP_STATIC(struct large_obj *, ptr_heap, 128);

/* 값 힙: 작은 타입에 적합 */
DEFINE_MIN_HEAP_STATIC(u64, val_heap, 128);

분기 예측(Branch Prediction) 힌트

/* likely/unlikely로 hot path 최적화 */
static inline int optimized_push(min_heap_t *heap,
        const void *elem, size_t sz,
        const struct min_heap_callbacks *f, void *args)
{
    /* 힙이 가득 찬 경우는 드묾 */
    if (unlikely(heap->nr >= heap->size))
        return -1;

    int pos = heap->nr++;
    memcpy(heap->data + pos * sz, elem, sz);

    /* 대부분의 삽입은 sift-up 없이 끝남 */
    if (likely(pos == 0 || !f->less(
            heap->data + pos * sz,
            heap->data + ((pos - 1) / 2) * sz, args)))
        return 0;

    min_heap_sift_up(heap, sz, f, args, pos);
    return 0;
}

프리페치 최적화

/* sift-down 시 다음 레벨 프리페치 */
while (1) {
    int left  = 2 * pos + 1;
    int right = 2 * pos + 2;

    /* 다다음 레벨 프리페치 (2 레벨 ahead) */
    if (4 * pos + 3 < heap->nr)
        prefetch(data + (4 * pos + 3) * elem_size);

    /* ... 비교 및 교환 ... */
}

모범 사례

• 크기 결정: 힙 크기를 가능한 한 컴파일 시점에 결정하여 DEFINE_MIN_HEAP_STATIC을 사용하세요. 동적 할당 시 kmalloc 실패를 반드시 처리합니다.
• 비교자 순수성: less()는 부수 효과(side effect)가 없어야 합니다. 전역 상태를 변경하거나 I/O를 수행하면 안 됩니다.
• 엄격한 약순서: less(a, b)와 less(b, a)가 동시에 true일 수 없어야 합니다. 동률일 때는 둘 다 false를 반환하세요.
• 락 보호: 힙에 대한 모든 접근(push/pop/peek 포함)은 동일한 락으로 보호해야 합니다.
• peek 포인터 수명: min_heap_peek() 반환 포인터는 다음 변경 연산 전까지만 유효합니다. 값이 필요하면 즉시 복사하세요.
• 인라인 최적화: hot path의 비교자/스왑 함수는 __always_inline을 적용하여 함수 호출 오버헤드를 제거합니다.
• 디버그 빌드: 개발 중에는 push/pop 후 min_heap_verify()를 호출하여 불변식을 검증합니다.

코드 리뷰 체크리스트

종합 요약 테이블

min_heap API 상세

커널 v6.5 이후 include/linux/min_heap.h에 정의된 min-heap API는 제네릭 매크로(Generic Macro) 기반으로 타입 안전성(Type Safety)을 보장합니다. 각 API의 내부 동작과 사용 패턴을 상세히 분석합니다.

DEFINE_MIN_HEAP 매크로

/* include/linux/min_heap.h */

/* 타입별 min_heap 정의 매크로 */
#define DEFINE_MIN_HEAP(type, name)          \
struct name {                                   \
    int nr;         /* 현재 원소 수 */        \
    int size;       /* 최대 용량 */          \
    type *data;     /* 원소 배열 포인터 */   \
    type preallocated[0]; /* 인라인 저장소 */ \
}

/* 사용 예: u64 타입의 min_heap */
DEFINE_MIN_HEAP(u64, my_u64_heap);

/* 스택에 인라인 저장소 포함 선언 */
DECLARE_MIN_HEAP(u64, 64) my_heap;
/* → nr=0, size=64, data=preallocated 배열 */

min_heap_push() 내부 동작

/* push 동작 단계 */
bool min_heap_push(struct min_heap *heap,
                   const void *element,
                   const struct min_heap_callbacks *funcs,
                   void *args)
{
    /* 1. 용량 초과 검사 */
    if (heap->nr >= heap->size)
        return false;  /* 실패: 힙 가득 참 */

    /* 2. 배열 끝에 원소 복사 */
    memcpy(heap->data + heap->nr * elem_size,
           element, elem_size);
    heap->nr++;

    /* 3. sift-up: 힙 속성 복원 */
    min_heap_sift_up(heap, heap->nr - 1, funcs, args);

    return true;
}

min_heap_pop() 내부 동작

/* pop 동작 단계 */
bool min_heap_pop(struct min_heap *heap,
                  const struct min_heap_callbacks *funcs,
                  void *args)
{
    if (heap->nr <= 0)
        return false;

    /* 1. 마지막 원소를 root(index 0)에 복사 */
    heap->nr--;
    memcpy(heap->data, heap->data + heap->nr * elem_size,
           elem_size);

    /* 2. sift-down: 힙 속성 복원 */
    min_heap_sift_down(heap, 0, funcs, args);

    return true;
}

min_heap_peek() — O(1) 최솟값 접근

/* peek: 단순 배열 첫 번째 원소 포인터 반환 */
static inline void *min_heap_peek(struct min_heap *heap)
{
    return heap->nr > 0 ? heap->data : NULL;
}

/* 사용 예 */
u64 *min_val = min_heap_peek(&my_heap);
if (min_val)
    pr_info("minimum = %llu\n", *min_val);

API 전체 요약

커스텀 비교 함수 작성

min_heap_callbacks의 less와 swp 함수 포인터를 통해 임의 타입의 비교와 교환을 커스터마이즈할 수 있습니다.

min_heap_callbacks 구조체

struct min_heap_callbacks {
    int elem_size;                        /* 원소 크기 (바이트) */
    bool (*less)(const void *lhs,
                 const void *rhs,
                 void *args);             /* 비교 함수 */
    void (*swp)(void *lhs,
                void *rhs,
                void *args);              /* 교환 함수 (NULL 가능) */
};

비교 함수 예제

/* 예제 1: 단순 u64 비교 */
static bool u64_less(const void *lhs, const void *rhs, void *args)
{
    return *(const u64 *)lhs < *(const u64 *)rhs;
}

/* 예제 2: 구조체 필드 기준 비교 */
struct task_entry {
    u64  deadline;     /* 정렬 기준 */
    pid_t pid;
    char  comm[16];
};

static bool task_less(const void *lhs, const void *rhs, void *args)
{
    const struct task_entry *a = lhs;
    const struct task_entry *b = rhs;
    return a->deadline < b->deadline;
}

/* 예제 3: 복합 키 비교 (deadline 동일 시 pid로 구분) */
static bool task_less_compound(const void *lhs, const void *rhs,
                               void *args)
{
    const struct task_entry *a = lhs;
    const struct task_entry *b = rhs;

    if (a->deadline != b->deadline)
        return a->deadline < b->deadline;
    return a->pid < b->pid;
}

/* 콜백 등록 */
static const struct min_heap_callbacks task_funcs = {
    .elem_size = sizeof(struct task_entry),
    .less = task_less_compound,
    .swp = NULL,   /* NULL이면 기본 memcpy swap 사용 */
};

커스텀 swap 함수

swp이 NULL이면 memcpy 기반 기본 교환이 사용됩니다. 원소에 부가 인덱스를 관리해야 하는 경우(perf_event 등) 커스텀 swap이 필요합니다:

/* perf_event 스타일: 위치 추적이 필요한 swap */
struct indexed_entry {
    u64 key;
    int *heap_index;    /* 역참조: 원소가 힙 내 몇 번째인지 */
};

static void indexed_swap(void *lhs, void *rhs, void *args)
{
    struct indexed_entry *a = lhs;
    struct indexed_entry *b = rhs;
    struct indexed_entry tmp;

    /* 1. 원소 교환 */
    tmp = *a;
    *a = *b;
    *b = tmp;

    /* 2. 역참조 인덱스 업데이트 */
    if (a->heap_index)
        *a->heap_index = ((char *)a - (char *)heap_base) / sizeof(*a);
    if (b->heap_index)
        *b->heap_index = ((char *)b - (char *)heap_base) / sizeof(*b);
}

커널 서브시스템 활용 상세

min-heap은 커널의 여러 핵심 서브시스템에서 우선순위 큐(Priority Queue)로 사용됩니다. 각 사용처의 구체적 패턴을 분석합니다.

perf_event 멀티플렉싱 상세

PMU(Performance Monitoring Unit) 카운터 수보다 모니터링할 이벤트가 많으면, perf는 min-heap을 사용하여 이벤트를 시분할 스케줄링합니다:

타이머 큐 활용

hrtimer 서브시스템은 rbtree를 기본 사용하지만, bcache와 같은 하위 시스템에서는 min-heap으로 만료 시간 기반 우선순위 큐를 구현합니다:

/* bcache 타이머 힙 사용 패턴 (drivers/md/bcache) */
struct bch_timer {
    u64 expires;         /* 만료 시간 (jiffies 또는 ktime) */
    void (*fn)(struct bch_timer *);
};

/* 비교: 가장 빨리 만료되는 타이머가 root */
static bool timer_less(const void *a, const void *b, void *args)
{
    return ((struct bch_timer *)a)->expires <
           ((struct bch_timer *)b)->expires;
}

/* 다음 만료 시간 O(1) 조회 */
struct bch_timer *next = min_heap_peek(&timer_heap);
if (next && time_after_eq(jiffies, next->expires)) {
    next->fn(next);
    min_heap_pop(&timer_heap, &timer_funcs, NULL);
}

CFS 런큐에서의 가능성

현재 CFS는 rbtree(rb_root_cached)를 사용하지만, EEVDF(Earliest Eligible Virtual Deadline First) 스케줄러로의 전환에서 min-heap이 논의되었습니다:

인라인 최적화와 제네릭 매크로

min-heap API는 헤더 파일에 static inline으로 정의되어 호출 오버헤드가 없습니다. 컴파일러가 비교 함수까지 인라인(Inline)하면 함수 포인터 호출 비용도 제거됩니다.

인라인 최적화 이점

타입 안전성 패턴

/* v6.5+ 타입 안전 매크로 */
DEFINE_MIN_HEAP(u64, u64_heap);

static struct u64_heap my_heap = {
    .data = (u64[128]){},
    .nr = 0,
    .size = 128,
};

/* 타입 불일치 시 컴파일 오류 발생 (v6.5+) */
u64 val = 42;
min_heap_push(&my_heap, &val, &u64_funcs, NULL);

/* 잘못된 타입 — 컴파일 경고/오류 */
u32 wrong = 42;
/* min_heap_push(&my_heap, &wrong, &u64_funcs, NULL); */
/* → 크기 불일치로 데이터 손상 위험 */

실전 커널 모듈 예제

min-heap API를 사용하는 완전한 커널 모듈 예제입니다. 우선순위 기반 작업 큐를 구현합니다.

/*
 * min_heap_demo.c -- min-heap 기반 우선순위 큐 데모
 *
 * 빌드: make -C /lib/modules/$(uname -r)/build M=$(pwd) modules
 * 로드: insmod min_heap_demo.ko
 * 로그: dmesg | grep heap_demo
 */

#include <linux/module.h>
#include <linux/min_heap.h>
#include <linux/random.h>

MODULE_LICENSE("GPL");

struct work_item {
    u32 priority;    /* 낮을수록 높은 우선순위 */
    u32 work_id;
};

static bool work_less(const void *a, const void *b, void *args)
{
    return ((const struct work_item *)a)->priority <
           ((const struct work_item *)b)->priority;
}

static const struct min_heap_callbacks work_funcs = {
    .elem_size = sizeof(struct work_item),
    .less = work_less,
    .swp = NULL,
};

#define HEAP_CAPACITY 64
static struct work_item heap_storage[HEAP_CAPACITY];
static struct min_heap work_heap = {
    .data = heap_storage,
    .nr = 0,
    .size = HEAP_CAPACITY,
};

static int __init heap_demo_init(void)
{
    struct work_item item, *top;
    int i;

    /* 20개 랜덤 우선순위 작업 삽입 */
    for (i = 0; i < 20; i++) {
        item.priority = get_random_u32() % 1000;
        item.work_id = i;
        min_heap_push(&work_heap, &item, &work_funcs, NULL);
        pr_info("heap_demo: pushed work_id=%u prio=%u\n",
                item.work_id, item.priority);
    }

    /* 최우선 작업 확인 */
    top = min_heap_peek(&work_heap);
    if (top)
        pr_info("heap_demo: top priority: id=%u prio=%u\n",
                top->work_id, top->priority);

    /* 우선순위 순서대로 5개 처리 */
    for (i = 0; i < 5 && work_heap.nr > 0; i++) {
        top = min_heap_peek(&work_heap);
        pr_info("heap_demo: processing id=%u prio=%u\n",
                top->work_id, top->priority);
        min_heap_pop(&work_heap, &work_funcs, NULL);
    }

    pr_info("heap_demo: %d items remaining\n", work_heap.nr);
    return 0;
}

static void __exit heap_demo_exit(void)
{
    work_heap.nr = 0;
    pr_info("heap_demo: cleaned up\n");
}

module_init(heap_demo_init);
module_exit(heap_demo_exit);

힙 vs 다른 자료구조 심층 비교

우선순위 큐가 필요할 때 min-heap, rbtree, 정렬 리스트 중 어떤 것을 선택해야 하는지 구체적 기준을 제시합니다.

힙 동시성 보호 패턴

min-heap API에는 내장 동기화가 없으므로, 멀티코어 환경에서는 호출자가 적절한 보호를 제공해야 합니다.

락 선택 가이드

/* 패턴 1: spinlock (인터럽트 컨텍스트 포함) */
static DEFINE_SPINLOCK(heap_lock);

void safe_push(struct work_item *item)
{
    unsigned long flags;
    spin_lock_irqsave(&heap_lock, flags);
    min_heap_push(&work_heap, item, &work_funcs, NULL);
    spin_unlock_irqrestore(&heap_lock, flags);
}

/* 패턴 2: per-CPU 힙 (경합 최소화) */
static DEFINE_PER_CPU(struct min_heap, percpu_heap);
static DEFINE_PER_CPU(struct work_item[64], percpu_storage);

void percpu_push(struct work_item *item)
{
    struct min_heap *heap;

    preempt_disable();
    heap = this_cpu_ptr(&percpu_heap);
    min_heap_push(heap, item, &work_funcs, NULL);
    preempt_enable();
}

/* 패턴 3: RCU + 복사-교체 (읽기 빈번) */
/* min-heap의 배열 특성 때문에 RCU 직접 적용은 어려움.
 * 전체 힙을 복사 후 교체하는 패턴이 필요하며,
 * 원소 수가 적을 때만 실용적. */

에러 처리 패턴

관련 문서

min-heap과 관련된 다른 자료구조 및 서브시스템을 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• Red-Black Tree — 커널의 범용 균형 이진 탐색 트리, min-heap과 가장 자주 비교되는 자료구조
• 연결 리스트 — 커널 자료구조의 기초, list_head와 hlist_head
• 프로세스 스케줄러 — CFS와 SCHED_DEADLINE에서의 우선순위 큐 활용
• 타이머 — hrtimer와 timer wheel의 내부 구현
• 메모리 관리(Memory Management) — kmalloc/vmalloc 등 힙 버퍼 할당 기반
• 동기화 기법 — 힙 접근 보호를 위한 락 선택 가이드
• Spinlock — 인터럽트 컨텍스트에서의 힙 보호
• RCU — 잠금(Lock) 없는 읽기 동기화, 힙과 결합된 동시성 패턴

참고 자료

• include/linux/min_heap.h — Bootlin Elixir — 커널 min-heap 헤더 파일의 전체 소스 코드를 확인할 수 있습니다. DEFINE_MIN_HEAP 매크로, push/pop/peek API 정의가 포함되어 있습니다.
• lib/min_heap.c — Bootlin Elixir — min-heap 라이브러리 구현부로, sift-up/sift-down 알고리즘과 heapify 로직의 실제 구현을 확인할 수 있습니다.
• lib/test_min_heap.c — Bootlin Elixir — 커널 내장 min-heap 단위 테스트 코드입니다. API 사용법을 파악하는 데 유용합니다.
• Generic data structures in the kernel (LWN.net) — 커널에서 사용되는 범용 자료구조에 대한 개요로, min-heap이 추가된 배경과 설계 철학을 다루고 있습니다.
• The min-heap API (LWN.net) — min-heap API가 커널에 도입된 과정과 perf 서브시스템에서의 활용 사례를 설명합니다.
• kernel/events/core.c — Bootlin Elixir — perf_event 서브시스템에서 min-heap을 사용하여 이벤트 스케줄링을 수행하는 실제 코드를 확인할 수 있습니다.
• kernel/sched/deadline.c — Bootlin Elixir — SCHED_DEADLINE(EDF) 스케줄러에서 우선순위 큐 기반 디스패칭이 구현된 소스입니다.
• Min Heap API — The Linux Kernel Documentation — 커널 공식 문서에서 제공하는 min-heap API 레퍼런스입니다.
• min_heap.h git log — kernel.org — min-heap 헤더의 커밋 이력을 통해 API 변경 과정을 추적할 수 있습니다.
• Binary heap — Wikipedia — 이진 힙 자료구조의 이론적 배경, 시간 복잡도 분석, 배열 기반 구현 원리를 설명합니다.