欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

【数据结构】C语言实现二叉树超详细入门(堆的实现，堆排序，TopK问题)

2026-03-09 分类：服务器技术 阅读(61) 评论(0)

上一篇我们详细介绍了数据结构中的数和二叉树的基本概念，理解了上一节的内容，这节理解的会更加深入，有需要的可以自行查看：

【数据结构】C语言实现二叉树超详细入门 (树，二叉树，堆的基本概念)-CSDN博客

目录

一.堆的实现

1.堆的创建

2.堆的初始化

3.堆的销毁

4.交换两个数据

5.向上调整

6.堆插入

7.向下调整

8.堆的根部删除

9.堆判空

10.返回根部元素

二.建堆的时间复杂度分析

1.向下调整建堆

2.向上调整建堆

三.堆的应用

1.堆排序

代码实现：

2.TopK问题

2.1堆排序

2.2把N个数建堆，取出前k个

2.3建一个k个数的小堆

一.堆的实现

用动态数组来实现

1.堆的创建

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

typedef int data;
typedef struct Heap
{
//用数组来表示二叉树
data* a;
int size;
int capacity;
}HP;

2.堆的初始化

//堆初始化
void HPInit(HP* php)
{
assert(php);
php->a = (data*)malloc(sizeof(data));
php->capacity = 1;
php->size = 0;
}

3.堆的销毁

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

4.交换两个数据

//交换两个数据
void swap(data* child, data* parent)
{
int temp = *child;
*child = *parent;
*parent = temp;
}

5.向上调整

用到向上调整其祖先一直到跟必须是大根堆或小根堆，这样才能不断向上比较，直到根部

//向上调整(在函数内部找父子叶)
void AdjustUp(data* a, int child)
{
assert(a);
int parent = (child – 1) / 2;
while (child > 0)//这里写parent >= 0也能运行，因为碰巧
{
//调整为大根堆，若想调整为小根堆，只用将 > 变为 <
if (a[child] < a[parent])
{
swap(&a[child],&a[parent]);
child = parent;
//这里parent不会小于0，所以下次循环a[child] = a[parent]，会走else，程序也能正常退出
parent = (child – 1) / 2;
}
else
{
break;
}
}
}

6.堆插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

//堆插入
void HPPush(HP* php, data x)
{
assert(php);
//判满
if (php->capacity == php->size)
{
data* temp = (data*)realloc(php->a, sizeof(data) * 2 * php->capacity);
if (temp == NULL)
{
perror("realloc fail");
}
php->a = temp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
//进行调整，变为大根堆或小根堆,用向上调整算法
AdjustUp(php->a, php->size-1);
}

7.向下调整

用到向下调整，从该子节点到叶子结点必须是大根堆或小根堆，这样才能不断向下比较，直到叶子结点

//向下调整(在函数内部找孩子叶)
void AdjustDown(data* a, int size, int parent)
{
//这里传入的size是为了判断是否到叶结点
int child = parent * 2 + 1;
//运用向下调整法，还需判断两个孩子哪一个最大（最小），然后再交换parent和child

while (child < size)
{
// 有右孩子 && 右孩子的数据大于(小于)左孩子
if (child + 1 < size && a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

8.堆的根部删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调 整算法。

//堆根部删除(将其换到最后一位删除)
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);
}

9.堆判空

//堆判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

10.返回根部元素

//返回根部数据
data HPTop(HP* php)
{
assert(php);
assert(php->size != 0);
return php->a[0];
}

———————————————————————————————————————————

二.建堆的时间复杂度分析

1.向下调整建堆

向下调整建堆 (从倒数第二行开始向下调) 的时间复杂度为O(N)

2.向上调整建堆

向上调整建堆（从第一行开始向上调）时间复杂度为O(N*logN)

巧记：

由于最后一层的结点个数站堆的一半，而向下调整建堆是从倒数第二层开始向下调整，所以不用调整最后一层，直接省了一半的结点移动，所以时间复杂度为O(N)；

同理，向上调整建堆是从第二层开始移动的，最后一层也要向上移动，只省略了根结点，相对移动的次数较多，所以时间复杂度为O(N*logN)。

———————————————————————————————————————————

三.堆的应用

1.堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  • 建堆

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

  • 利用堆删除思想来进行排序

    • 建堆和堆删除中都用到了向下调整，并且向下调整建堆的时间复杂度较小，因此掌握了向下调整，就可以完成堆排序。

    代码实现：

    #define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<assert.h>

    typedef int data;
    typedef struct Heap
    {
    //用数组来表示二叉树
    data* a;
    int size;
    int capacity;
    }HP;

    //交换两个数据
    void Swap(data* child, data* parent)
    {
    int temp = *child;
    *child = *parent;
    *parent = temp;
    }
    //向上调整(在函数内部找父子叶)
    void AdjustUp(data* a, int child)
    {
    assert(a);
    int parent = (child – 1) / 2;
    while (child > 0)//这里写parent >= 0也能运行，因为碰巧
    {
    //调整为大根堆，若想调整为小根堆，只用将 > 变为 <
    if (a[child] < a[parent])
    {
    Swap(&a[child], &a[parent]);
    child = parent;
    //这里parent不会小于0，所以下次循环a[child] = a[parent]，会走else，程序也能正常退出
    parent = (child – 1) / 2;
    }
    else
    {
    break;
    }
    }
    }
    //向下调整(在函数内部找孩子叶)
    void AdjustDown(data* a, int size, int parent)
    {
    //这里传入的size是为了判断是否到叶结点
    int child = parent * 2 + 1;
    //运用向下调整法，还需判断两个孩子哪一个最大（最小），然后再交换parent和child

    while (child < size)
    {
    // 有右孩子 && 右孩子的数据大于(小于)左孩子
    if (child + 1 < size && 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 HeapSort(int* arr, int n)
    {
    //直接对数组进行建堆，直接把0看成根，下面的每个孩子跟父子叶进行比较就可以排成堆
    //for (int i = 1; i < n; i++)
    //{
    //AdjustUp(arr, i);
    //}

    ////降序，建小堆,向上调，时间复杂度为O(N*logN)
    //for (int i = 1; i < n; i++)
    //{
    //AdjustUp(arr, i);
    //}

    //1.建小根堆
    //降序，建小堆,向下调，时间复杂度为O(N)
    for (int i = (n – 1 – 1) / 2; i >= 0; i–)
    {
    AdjustDown(arr, n, i);
    }

    //2.将最小的结点元素放在最后一个，在进行向下调整将倒数第二小的放在根部，以此循环，直到最大的在根部
    int end = n – 1;
    while (end)
    {
    Swap(&arr[0], &arr[end]);
    //向下调整
    AdjustDown(arr, end, 0);
    //end–相当于把最后一个数据删除，不考虑
    end–;
    }
    }
    int main()
    {
    int arr[] = { 1,2,5,6,92,3,5,6,52,99,4555,57,236,5115,56 };
    HeapSort(arr, sizeof(arr) / sizeof(int));
    return 0;
    }

    2.TopK问题

    TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

    比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

    以求国服韩信前十的玩家为例来实现TopK问题

    2.1堆排序

    上面已将提到过了，这里就不再过多介绍了。

    时间复杂度：O(N+NlogN) 空间复杂度：O(N)，能否将其再优化了？肯定是可以的，下面看方法二。

    2.2把N个数建堆，取出前k个

    注意点： 1.取出数据后要让其与最后的元素替换，因为你已经取出这个元素了，所以不需要它了，这时让它去堆尾，不让它算入堆的个数中就行了。为什么要这样做了，因为这样既保证了堆的结构，也相当于把这个取出来的数删除了。 2. 如果在取到堆顶数据后直接删除数据，那么就要重新建堆了。正确的做法应该是上面所说的方法，因为那样只要进行一次向下调整，就可以保证堆的结构了。要知道建堆的复杂度为O(N),而一次向下调整的复杂度仅为O（logN），这样大大提升了效率。

    #define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<assert.h>

    typedef int data;
    typedef struct Heap
    {
    //用数组来表示二叉树
    data* a;
    int size;
    int capacity;
    }HP;

    //交换两个数据
    void Swap(data* child, data* parent)
    {
    int temp = *child;
    *child = *parent;
    *parent = temp;
    }

    //向下调整(在函数内部找孩子叶)
    void AdjustDown(data* a, int size, int parent)
    {
    //这里传入的size是为了判断是否到叶结点
    int child = parent * 2 + 1;
    //运用向下调整法，还需判断两个孩子哪一个最大（最小），然后再交换parent和child

    while (child < size)
    {
    // 有右孩子 && 右孩子的数据大于(小于)左孩子
    if (child + 1 < size && a[child] < a[child + 1])
    {
    child++;
    }
    if (a[child] > a[parent])
    {
    Swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
    }
    else
    {
    break;
    }
    }
    }
    //返回根部数据
    data HPTop(data* arr)
    {
    return arr[0];
    }

    //堆根部删除(将其换到最后一位删除)
    void HPPop(data*arr,int size)
    {
    //交换根部数据和最后一个数据
    Swap(&arr[0],&arr[size-1]);
    size–;
    AdjustDown(arr, size, 0);
    }

    //在原数组上建堆，不用额外开辟空间了
    void HeapSort(int* arr, int n)
    {
    //建大堆,向下调，时间复杂度为O(N)
    for (int i = (n – 1 – 1) / 2; i >= 0; i–)
    {
    AdjustDown(arr, n, i);
    }
    //找出最大的前k项
    int k = 10;
    while (k–)
    {
    printf("%d ", HPTop(arr));
    HPPop(arr,n);
    n–;
    }

    }
    int main()
    {
    int arr[] = { 1,2,5,6,92,3,5,6,52,99,4555,57,236,5115,56 };
    HeapSort(arr, sizeof(arr) / sizeof(int));
    return 0;
    }

    此时时间复杂度为O(N)，但是若N的数值很大时所占用的内存空间较大，有没有即能提高时间效率，又能减少空间消耗，那我们来看第三种方法

    2.3建一个k个数的小堆

    先建一个k个数的小堆，然后将数组中n-k个元素依次与堆顶的元素比较，若比堆顶元素大，则将堆顶元素删除，然后将这个数插入到堆中，这儿要注意：插入这个数到堆中的时候，要使用向下排序算法保证堆的结构不被破坏，把第一大的数放在堆底，重复该操作。到最后，堆里面的k个数就是最大的k个数了。

    #define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<assert.h>

    typedef int data;
    typedef struct Heap
    {
    //用数组来表示二叉树
    data* a;
    int size;
    int capacity;
    }HP;

    //交换两个数据
    void Swap(data* child, data* parent)
    {
    int temp = *child;
    *child = *parent;
    *parent = temp;
    }

    //向下调整(在函数内部找孩子叶)
    void AdjustDown(data* a, int size, int parent)
    {
    //这里传入的size是为了判断是否到叶结点
    int child = parent * 2 + 1;
    //运用向下调整法，还需判断两个孩子哪一个最大（最小），然后再交换parent和child

    while (child < size)
    {
    // 有右孩子 && 右孩子的数据大于(小于)左孩子
    if (child + 1 < size && a[child] > a[child + 1])
    {
    child++;
    }
    if (a[child] < a[parent])
    {
    Swap(&a[child], &a[parent]);
    parent = child;
    child = parent * 2 + 1;
    }
    else
    {
    break;
    }
    }
    }
    //返回根部数据
    data HPTop(data* arr)
    {
    return arr[0];
    }

    //堆根部删除(将其换到最后一位删除)
    void HPPop(data*arr,int size)
    {
    //交换根部数据和最后一个数据
    Swap(&arr[0],&arr[size-1]);
    size–;
    AdjustDown(arr, size, 0);
    }

    //在原数组上建堆，不用额外开辟空间了
    void HeapSort(int* arr, int n)
    {
    //建立k个数的小堆
    int k = 10;
    int* kminheap = (int*)malloc(sizeof(int) * k);
    if (kminheap == NULL)
    {
    perror("malloc fail");
    exit(1);
    }
    for (int i = 0; i < k; i++)
    {
    kminheap[i] = arr[i];
    }
    for (int i = k; i < n; i++)
    {
    if (arr[i] > kminheap[0])
    {
    Swap(&arr[i], &kminheap[0]);
    AdjustDown(kminheap, k, 0);
    }
    }
    }
    int main()
    {
    int arr[] = { 1,2,5,6,92,3,5,6,52,99,4555,57,236,5115,56 };
    HeapSort(arr, sizeof(arr) / sizeof(int));
    return 0;
    }

    时间复杂度：O（k+n*logk） 空间复杂度：O（n） 与之前两种方法对比，这种方法大大提高了效率。

    如果对你有帮助，欢迎 点赞、收藏、关注，后续持续更新数据结构与算法！

    下一篇主要讲解二叉树链式结构实现

    赞(0)
    未经允许不得转载：171主机测评 » 【数据结构】C语言实现二叉树超详细入门(堆的实现，堆排序，TopK问题)
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(58971)#python(20022)#开发语言(16797)#java(15415)#运维(15314)#linux(14911)#大数据(14530)#服务器(13026)#算法(11742)#前端(10849)#网络(9338)#数据库(8855)#ai(8849)#c++(8145)#课程设计(6793)#学习(6738)#机器学习(6691)#区块链(5907)#OpenClaw(5387)#后端(5121)#spring boot(4991)#深度学习(4927)#c语言(4365)#毕业设计(4291)#数据结构(4187)#安全(4032)#docker(3919)#架构(3841)#javascript(3795)#大模型(3639)

    热门文章

    最新文章

    归档

    分类