数据结构初阶：堆的实现 | 极客日志

C算法

数据结构初阶：堆的实现

使用顺序结构实现堆（完全二叉树）的方法。堆具有排序和解决 TOP-K 问题的功能，分为大根堆和小根堆。内容涵盖初始化、插入（向上调整）、删除堆顶（向下调整）的核心逻辑及代码实现。重点讲解了向上调整和向下调整的算法步骤、时间复杂度分析以及边界条件处理，并提供了完整的 C 语言代码示例，包括头文件、测试文件和实现文件。

极客零度发布于 2026/3/28更新于 2026/4/185 浏览

数据结构初阶：堆的实现

堆是使用顺序结构实现的完全二叉树，除了存储数据外，还具有排序和解决 TOP-K 问题的功能。

小根堆的堆顶数据最小，大根堆的堆顶数据最大。通过不断选出最大/最小值，可实现排序或获取前 K 个元素。

一、初始化

将交换操作封装为函数以便复用。

Heap.h

typedef int HPDataTypt;
typedef struct Heap {
    HPDataTypt* a; // 数组指针，指向存储数据的数组
    int size;      // 当前已存储的有效数据个数
    int capacity;  // 最大容量
} HP;

void HeapInit(HP* php); // 初始化
void HeapDestroy(HP* php); // 销毁

Heap.c

void HeapInit(HP* php) {
    assert(php);
    php->a = (HPDataTypt*)malloc(sizeof(HPDataTypt) * 4);
    if (php->a == NULL) {
        perror("malloc fail");
        return;
    }
    php->size = 0;
    php->capacity = 4;
}

void Swap(HPDataTypt* p1, HPDataTypt* p2) {
    HPDataTypt tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

参数 php 指向主函数中 HP 结构体变量的地址。若为空说明结构体未分配，需断言检查。

二、插入

堆的底层是数组。插入数据后需调整以保持堆性质（以大根堆为例）。

文章配图

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

void AdjustUp(HPDataTypt* a, int child) // 从孩子位置向上调整
{
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] > a[parent]) // 娃 > 爸，往上走，交换
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break; // 娃 <= 爸，不往上走
        }
    }
}

void HeapPush(HP* php, HPDataTypt x) {
    assert(php);
    if (php->size == php->capacity) {
        HPDataTypt* tmp = (HPDataTypt*)realloc(php->a, sizeof(HPDataTypt) * php->capacity * 2);
        if (tmp == NULL) {
            perror("malloc fail");
            return;
        }
        php->a = tmp;
        php->capacity *= 2;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1); // 从孩子位置向上调整
}

void AdjustDown(HPDataTypt* a, int n, int parent) {
    int child = parent * 2 + 1; // 默认左孩子大
    while (child < n) {
        // 选出左右孩子中大的那一个
        if (child + 1 < n && a[child] < a[child + 1]) // 防止无右娃的越界风险
        {
            child++; // 如果右孩子大，++后，child 就是右孩子
        }
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void HeapPop(HP* php) {
    assert(php);
    assert(!HeapEmpty(php));
    Swap(&php->a[0], &php->a[php->size - 1]); // 交换堆顶、最后元素
    php->size--; // 删除换下来的原堆顶元素
    AdjustDown(php->a, php->size, 0); // 向下调整
}

typedef int HPDataTypt;
typedef struct Heap {
    HPDataTypt* a;
    int size;
    int capacity;
} HP;

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataTypt x);
void HeapPop(HP* php);
HPDataTypt HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
void AdjustUp(HPDataTypt* a, int child);
void AdjustDown(HPDataTypt* a, int n, int parent);

void test1() // 排序
{
    HP hp;
    HeapInit(&hp);
    HeapPush(&hp, 2);
    HeapPush(&hp, 45);
    HeapPush(&hp, 76);
    HeapPush(&hp, 23);
    HeapPush(&hp, 5654);
    HeapPush(&hp, 24);
    HeapPush(&hp, 5);
    HeapPush(&hp, 242);
    HeapPush(&hp, 25);
    while (!HeapEmpty(&hp)) {
        printf("%d ", HeapTop(&hp));
        HeapPop(&hp);
    }
    HeapDestroy(&hp);
}

void test2() // top-k
{
    HP hp;
    HeapInit(&hp);
    HeapPush(&hp, 2);
    HeapPush(&hp, 45);
    HeapPush(&hp, 76);
    HeapPush(&hp, 23);
    HeapPush(&hp, 5654);
    HeapPush(&hp, 24);
    HeapPush(&hp, 5);
    HeapPush(&hp, 242);
    HeapPush(&hp, 25);
    HeapPush(&hp, 5);
    HeapPush(&hp, 5);
    int k = 0;
    scanf("%d", &k);
    while (!HeapEmpty(&hp) && k--) {
        printf("%d ", HeapTop(&hp));
        HeapPop(&hp);
    }
    HeapDestroy(&hp);
}

void HeapInit(HP* php) {
    assert(php);
    php->a = (HPDataTypt*)malloc(sizeof(HPDataTypt) * 4);
    if (php->a == NULL) {
        perror("malloc fail");
        return;
    }
    php->size = 0;
    php->capacity = 4;
}

void Swap(HPDataTypt* p1, HPDataTypt* p2) {
    HPDataTypt tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustUp(HPDataTypt* a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else {
            break;
        }
    }
}

void HeapPush(HP* php, HPDataTypt x) {
    assert(php);
    if (php->size == php->capacity) {
        HPDataTypt* tmp = (HPDataTypt*)realloc(php->a, sizeof(HPDataTypt) * php->capacity * 2);
        if (tmp == NULL) {
            perror("malloc fail");
            return;
        }
        php->a = tmp;
        php->capacity *= 2;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

void AdjustDown(HPDataTypt* a, int n, int parent) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child] < a[child + 1]) {
            child++;
        }
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void HeapPop(HP* php) {
    assert(php);
    assert(!HeapEmpty(php));
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}

HPDataTypt HeapTop(HP* php) {
    assert(php);
    return php->a[0];
}

bool HeapEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}

int HeapSize(HP* php) {
    assert(php);
    return php->size;
}

void HeapDestroy(HP* php) {
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}