《数据结构二叉树之堆 —— 优先队列与排序的高效实现（2）》

用户11983512

发布于 2026-01-09 14:34:16

700

文章被收录于专栏：用户11983512的专栏用户11983512的专栏

前言

嗨(*･ω< ) ，上一篇我们初识了数据结构之初识二叉树（1）——核心概念入门，并了解了二叉树。今天我们来学习二叉树的一种——堆，并用顺序结构实现。好啦，让我们来见证它的实现过程吧！

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

一、堆的概念

如果有一个关键码的集合K = {k₀，k₁，k₂，…，kₙ₋₁}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Kᵢ <= K₂ᵢ₊₁且Kᵢ <= K₂ᵢ₊₂（Kᵢ >= K₂ᵢ₊₁且Kᵢ >= K₂ᵢ₊₂）i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

相当于小堆为小辈大或等于，大堆长辈大或等于

二、堆相关方法的实现

堆的实现用数组实现，我们上一篇说了我们利用这个来实现

下面我们用Heap.h作为头文件声明，Heap.c实现头文件函数功能，test.c用来测试

1、堆结构的创建

用数组实现，所以我们构建一个堆的结构 Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;//当前元素个数
    int capacity;//总空间大小
}HP;

2、初始化和销毁

这种类型的初始化和销毁我们已经练习了，很多遍了，这里就不详细解释了 Heap.c 初始化

void HPInit(HP* php)//初始化
{
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
}

销毁

void HPDestroy(HP* php)//销毁
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

3、堆的插入（向上调整法）

所谓堆的插入，就是按照堆的规则进行插入，这里我们选择实现小堆的插入对堆的插入我们就要了解一个方法——向上调整法

向上调整法：

1.先将元素插入到堆的末尾，即最后一个孩子之后 2.插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适位置即可过程如图

如上图所示，我们知道数组元素个数及孩子下标i，可通过计算父亲下标(i-1)/2(前面第二部分开头推倒过）来进行比较，并交换，实现堆的插入

代码实现

我们在插入时，和以前一样都需要先判断空间是否满了，再扩容，插入，现在还要新定义2个函数，一个进行孩子与父亲进行比较，一个实现交换代码如下 Heap.c

// 交换两个HPDataType类型变量的值
// p1：指向第一个变量的指针
// p2：指向第二个变量的指针
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;  // 用临时变量保存p1指向的值
    *p1 = *p2;             // 将p2指向的值赋给p1指向的变量
    *p2 = tmp;             // 将临时变量（原p1的值）赋给p2指向的变量
}

// 向上调整函数：用于维护小根堆性质（子节点值不小于父节点值）
// 当新元素插入堆尾后，通过向上调整使其“上浮”到正确位置
// a：堆的底层数组
// child：新插入元素（需要调整的节点）在数组中的下标
void AdjustUp(HPDataType* a, int child)
{
    // 计算child的父节点下标：完全二叉树中，父节点下标 = (子节点下标 - 1) / 2（整数除法）
    int parent = (child - 1) / 2;

    // 循环条件：child > 0（当child为0时，已到达根节点，无需继续调整）
    while (child > 0)
    {
        // 小根堆性质：若子节点值 < 父节点值，说明违反堆性质，需要交换
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);  // 交换子节点与父节点的值
            child = parent;               // 更新child为原父节点下标（继续向上检查）
            parent = (child - 1) / 2;     // 重新计算新child的父节点下标
        }
        else
        {
            // 若子节点值 >= 父节点值，说明已满足堆性质，退出循环
            break;
        }
    }
}

// 向堆中插入元素
// php：指向堆结构的指针（包含堆的数组、大小、容量信息）
// x：要插入的元素值
void HPPush(HP* php, HPDataType x)
{
    assert(php);  // 断言堆结构指针非空，避免空指针访问

    // 检查堆是否已满（当前元素个数 == 容量），若满则扩容
    if (php->size == php->capacity)
    {
        // 计算新容量：若初始容量为0（未初始化），则设为4；否则扩容为原来的2倍
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        // 重新分配内存（realloc会保留原有数据）
        HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
        if (tmp == NULL)  // 内存分配失败处理
        {
            perror("realloc fail");  // 打印错误信息
            return;  // 分配失败则不插入元素，直接返回
        }

        php->a = tmp;  // 更新堆的数组指针为新分配的内存
        php->capacity = newcapacity;  // 更新堆的容量为新容量
    }

    // 将新元素插入到堆的末尾（数组的size位置）
    php->a[php->size] = x;
    php->size++;  // 堆的元素个数加1

    // 新元素插入后可能破坏堆性质，调用向上调整函数使其归位
    // 调整的起始下标为最后一个元素（即刚插入的元素，下标为size-1）
    AdjustUp(php->a, php->size - 1);
}

测试

这时我们需要对堆的插入进行测试这里对数组中每个元素都当成插入 test.c

#include"Heap.h"

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }
    HPDestroy(&hp);
}
int main()
{
    TestHeap1();
    return 0;
}

结果

排成树就是如下

可以看出每个父亲结点的数据都小于等于对应孩子节点，这刚好符合了小堆的性质，证明代码实现正确

4、堆的删除(向下调整方法)

说到堆的删除，是堆顶的删除，堆尾的删除没用，这里可不简单，并不是简单的删除，如果只删除，那就不是树的结构了，那有人会说那就把数据整体向前移动一位不就行了吗？这可更不对了，这会严重影响堆的结构，使他不是一个堆结果如图,显而易见,这种方法是错的

所以我们应该怎么删除呢,这就要引入一个新方法——向下调整方法

向下调整方法

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。过程： 1.将堆顶元素与堆中最后一个元素进行交换 2.删除堆中最后一个元素 3.将堆顶元素向下调整到满足堆特性为止

过程如下图

这样就变成了只需要删除尾部元素就可以了，而尾部删除只需要size–(元素个数-1）就行啦向下调整法与向上调整法十分相似，但是向下调整法是与较小的孩子进行交换，通过父亲找孩子，不断进行比较交换来完成，也十分简单，代码如下： Heap.c

// 交换两个HPDataType类型变量的值
// p1：指向第一个变量的指针；p2：指向第二个变量的指针
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;  // 用临时变量暂存p1指向的值
    *p1 = *p2;             // 将p2的值赋给p1
    *p2 = tmp;             // 将临时变量（原p1的值）赋给p2
}

// 向下调整函数：用于维护小根堆性质（父节点值 ≤ 子节点值）
// 当父节点可能违反堆性质时，通过与子节点比较交换，让父节点“下沉”到正确位置
// a：堆的底层数组；n：堆中有效元素的个数（用于判断子节点是否越界）；parent：需要调整的父节点下标
void AdjustDown(HPDataType* a, int n, int parent)
{
    // 1. 先假设左子节点是较小的孩子（完全二叉树中，左子节点下标=parent*2+1）
    int child = parent * 2 + 1;

    // 循环条件：child < n（当child >= n时，说明当前parent没有子节点，已调整到叶子节点，无需继续）
    while (child < n)
    {
        // 2. 找出左右子节点中较小的那个（如果右子节点存在且更小，则更新child为右子节点下标）
        // 注意：右子节点下标=child+1，需先判断右子节点是否存在（child+1 < n）
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;  // 右子节点更小，更新child为右子节点下标
        }

        // 3. 比较父节点与较小子节点的值：若父节点值 > 子节点值，违反小根堆性质，需交换
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);  // 交换父节点与子节点的值
            parent = child;               // 更新parent为当前子节点下标（继续向下检查）
            child = parent * 2 + 1;       // 重新计算新parent的左子节点下标
        }
        else
        {
            // 若父节点值 ≤ 子节点值，已满足堆性质，退出循环
            break;
        }
    }
}

// 堆的删除操作（删除堆顶元素，时间复杂度O(logN)）
// 堆的删除默认删除堆顶元素（小根堆中为最小值），通过“交换+调整”维持堆结构和性质
void HPPop(HP* php)
{
    assert(php);               // 断言堆结构指针非空
    assert(php->size > 0);     // 断言堆非空（至少有一个元素可删除）

    // 1. 交换堆顶元素（下标0）与最后一个元素（下标size-1）
    // 目的：将堆顶元素“移到”数组末尾，后续只需删除末尾元素，避免破坏完全二叉树结构
    Swap(&php->a[0], &php->a[php->size - 1]);

    // 2. 缩小堆的大小（size--），相当于删除原堆顶元素（此时已在末尾）
    php->size--;

    // 3. 对新的堆顶元素（原末尾元素）执行向下调整，恢复堆的性质
    // 因为交换后新堆顶可能违反堆性质，需通过AdjustDown使其“下沉”到正确位置
    AdjustDown(php->a, php->size, 0);
}

测试

test.c 这里还是与上面测试插入代码相同，只是加了一个堆的删除

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }
    HPPop(&hp);
    HPDestroy(&hp);
}
int main()
{
    TestHeap1();

    return 0;
}

在HPPop删除堆头之前

改为树的图如下

除了最后一个（主要是调试我访问的是10个元素，通常我们访问通过size访问，我们不会访问到最后被删除的元素）都满足小堆，所以代码正确实现。堆顶删除数据的作用：我们发现堆顶数据为最小数据，堆顶的删除使第2小的元素为堆顶，便于我们找到前多少小的元素，在数据大时比较节省运行时间

5、取堆顶元素

这个就比较简单了，直接访问下标为0的元素代码如下 Heap.c

HPDataType HPTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

这个与堆的删除结合起来，就可以完成访问前k个小的元素

6、堆的判空

这也非常简单，只需要看size是否为空就行啦代码如下： Heap.c

bool HPEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}

7、总测试

这里再测试一下取堆顶元素，和判空 test.c

#include"Heap.h"

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }
    printf("%d\n", HPTop(&hp));
    if (HPEmpty(&hp) == 0)
    {
        printf("空\n");
    }
    HPDestroy(&hp);
}

int main()
{
    TestHeap1();

    return 0;
}

结果

验证正确

8、总代码

好啦，堆的实现到这里就完成啦，我们根据堆的功能所需，来实现，这里就是总代码啦 Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>


typedef int HPDataType;

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

void Swap(HPDataType* p1, HPDataType* p2);//交换
void AdjustUp(HPDataType* a, int child);//向上调整法
void AdjustDown(HPDataType* a, int n, int parent);向下调整法

void HPInit(HP* php);//初始化
void HPDestroy(HP* php);//堆的销毁
void HPPush(HP* php, HPDataType x);//插入
void HPPop(HP* php);//删除堆顶元素
HPDataType HPTop(HP* php);//返回堆顶元素
bool HPEmpty(HP* php);//判空

Heap.c

#include"Heap.h"

// 初始化堆：将堆的数组、大小、容量置为初始状态
void HPInit(HP* php)
{
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
}

// 销毁堆：释放堆的动态数组内存，还原堆的初始状态
void HPDestroy(HP* php)
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

// 交换两个HPDataType类型变量的值，用于堆调整时的元素交换
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 向上调整堆：用于小根堆，使新插入的元素（或被修改的元素）上浮到正确位置，维持堆性质
void AdjustUp(HPDataType* 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 HPPush(HP* php, HPDataType x)
{
    assert(php);

    if (php->size == php->capacity)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }

        php->a = tmp;
        php->capacity = newcapacity;
    }

    php->a[php->size] = x;
    php->size++;

    AdjustUp(php->a, php->size - 1);
}

// 向下调整堆：用于小根堆，使父节点（或被修改的节点）下沉到正确位置，维持堆性质
void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = parent * 2 + 1;

    while (child < n)
    {
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;
        }

        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

// 删除堆顶元素：交换堆顶与堆尾元素 + 缩小堆大小 + 向下调整堆以维持性质
void HPPop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;

    AdjustDown(php->a, php->size, 0);
}

// 获取堆顶元素的值（不删除）
HPDataType HPTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

// 判断堆是否为空
bool HPEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}

test.c

#include"Heap.h"

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }
    printf("%d\n", HPTop(&hp));
    if (HPEmpty(&hp) == 0)
    {
        printf("空\n");
    }
    HPDestroy(&hp);
}

int main()
{
    TestHeap1();

    return 0;
}

9、获取前k个小的元素

我在堆的删除和取堆顶元素时提到可以用这些功能来实现获取前k个小的元素，现在我们就来实现的来啦 test .c

#include"Heap.h"

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }
    int k;
    scanf("%d",&k);
    while(k--)
    {
      printf("%d ", HPTop(&hp)); 
		  HPPop(&hp);
    }
    HPDestroy(&hp);
}

int main()
{
    TestHeap1();

    return 0;
}

当k=3时，结果如下

的确是最小的三个，这就实现啦，相反想找到最大的几个需要建大堆

三、堆的应用（堆排序）

1、堆排序（无限制）

通过第三部分最后一段，我们可以得到有序的数据，但它只是通过打印的方式进行呈现，所以我们需要将排序好的放在数组中

#include"Heap.h"

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        a[i]=HPTop(&hp);
        HPPop(&hp);
    }
    for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        printf("%d ", a[i]);
    }

    
    HPDestroy(&hp);
}
int main()
{
    TestHeap1();

    return 0;
}

结果如下

这段代码的空间复杂度为O(n)，因为创建了一个堆来存放数组元素，那有没有一种方法可以不用创建堆也能进行排序呀，答案是一定的，方法如下：

2、堆排序（不用堆进行存储）

我们需要用堆结构的思想，而不用堆的结构 这时我们需要对数组直接进行操作，这时我们需要考虑我们想要创建升序的数组，我们要建大堆还是小堆呢？大家可能会觉得应该建小堆，因为小堆每次获取堆顶数据都是最小的，但是这种方法会有很大的缺陷：

效率低：每次交换后剩余小堆的调整需重新从下向上构建，而且堆的范围需要频繁从数组开头，边界处理的额外开销增加，导致运行效率低
直接得到降序结果：他会每次将最小的元素放在数组尾部，导致最后得到的是降序结构这时我们就应该怎么办呢，那我们就用大堆排序，每次将最大的放在数组尾部，符合降序规则这时我们可以得出结论：

升序：建大堆 降序：建小堆

因为我们要建升序，所以我们要建大堆，之前我们建的都是小堆，这里把向下调整方改为大堆的就可以了（对于第一个循环建堆阶段，一般使用向下调整法会更高效，因为从底部的非叶子节点开始调整，能更快地构建出符合要求的堆。而向上调整法一般更适用于插入单个元素时的调整）这里空间复杂度为O(1),因为没有建额外的空间 Heap.c

void AdjustDown(HPDataType* a, int n, int parent)
{
    // 先假设左孩子小
    int child = parent * 2 + 1;

    while (child < n)  // child >= n说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }

        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

test.c

#include"Heap.h"
// 堆排序    O(N*logN)
// 冒泡排序  O(N^2) 
void HeapSort(int* a, int n)
{
    // 降序，建小堆
    // 升序，建大堆

    for (int i = (n - 1 - 1) / 2; i >= 0; i--)//这里n-1为孩子下标，再-1/2为父亲下标
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}

void TestHeap2()
{
    int a[] = { 4,2,8,1,5,6,9,7,2,7,9 };
    HeapSort(a, sizeof(a) / sizeof(int));
}

int main()
{
    TestHeap2();

    return 0;
}

正确实现啦这里我们再进行降序，只需要将向下调整方改一下比较方法，改为小堆就行啦 Heap.c

void AdjustDown(HPDataType* a, int n, int parent)
{
    // 先假设左孩子小
    int child = parent * 2 + 1;

    while (child < n)  // child >= n说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;
        }

        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

结果