【数据结构】堆、大根堆、小根堆与堆排序（C语言实现）

最新推荐文章于 2024-10-07 22:24:24 发布

魔理沙偷走了BUG

最新推荐文章于 2024-10-07 22:24:24 发布

阅读量4.2k

点赞数 3

分类专栏：数据结构文章标签：数据结构 c语言算法排序算法开源

本文链接：https://blog.csdn.net/qq_30204431/article/details/126982814

版权

数据结构专栏收录该内容

9 篇文章

订阅专栏

本文介绍了完全二叉树及大根堆的概念，探讨了大根堆的抽象数据类型、初始化、插入和删除操作，并实现了堆排序算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1. 基本概念

1. 1 完全二叉树

深度为 $k$ 的具有 $n$ 个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为 $1$ ~ $n$ 的结点一一对应时，称之为完全二叉树。

1. 2 完全二叉树的性质

（版权声明：此PPT截图是我参加本科时期的学校组织的自学自讲活动用的PPT，未经允许禁止用于商业用途）
完全二叉树的性质

1. 3 二叉树的顺序存储

（版权声明：此PPT截图是我参加本科时期的学校组织的自学自讲活动用的PPT，未经允许禁止用于商业用途）
二叉树的顺序存储
完全二叉树无需补0，按完全二叉树的定义，我们知道，完全二叉树按层次遍历，从上到下，从左到右，到最后一个叶子结点就是数组的末端。

1. 4 堆

堆是一种用完全二叉树表示的数据结构，它分为大根堆和小根堆两种类型。

1. 5 大根堆与小根堆

大根堆就是指在完全二叉树中，每一个双亲（分支）结点的值要大于其（左右）孩子结点的值，根据完全二叉树的性质我们可以知道：
已知双亲结点的值为 $H (n)$ ，其中 $n$ 为序号（不是下标，从1开始），则 $H (n) > H (2 n)$ 且 $H (n) > H (2 n + 1)$ ，如图所示：

而小根堆则相反，要求 $H (n) < H (2 n)$ 且 $H (n) < H (2 n + 1)$ ，示意图还是上图。
也就是说，大根堆要求越接近根结点的结点值越大，其孩子结点越小，小根堆则是越接近根结点的结点值越小，其孩子结点的值比双亲结点大。

2. 堆数据结构（以大根堆为例）

具体思路详见代码注释。

2.1 大根堆的抽象数据类型（Abstract Data Type，ADT）

下面根据上述定义，给出大根堆的数据结构的定义（C语言结构体），本文实现的是一个动态的堆，长度是可变的，不是静态的数组。

//大根堆数据结构（一个用一维数组构建的完全二叉树），根结点大，孩子结点都比根结点小
typedef struct MaxHeap {
    int len;//堆长度
    int* tree;//存储完全二叉树的数组
}MaxHeap;

2.2 大根堆的初始化

//初始化一个大根堆
MaxHeap* newMaxHeap()
{
    //最开始堆中无元素，所以堆长度为0，堆中的完全二叉树为空树
    MaxHeap* p = (MaxHeap*)malloc(sizeof(MaxHeap));
    if (p == NULL)
    {
        return NULL;
    }
    p->len = 0;
    p->tree = NULL;
    return p;
}

2.3 大根堆的插入操作

插入的时候要保证堆满足大根堆的定义，即双亲结点的值永远大于孩子结点的值，对于插入操作，先将待插入元素放置在堆底，然后对比它的双亲结点，如果双亲结点比新入堆结点的值小，就把它和双亲结点互换，以此保证双亲结点的值永远大于孩子结点的值，否则，就不换，通过完全二叉树的性质，我们可以知道，一个下标为i的结点，其双亲结点的下标为i/2的向下取整，根据这些性质，C语言实现的大根堆插入算法代码如下（详细思路见代码注释）：

//入大根堆（堆的插入操作）
void pushMaxHeap(MaxHeap* maxHeap, int data)
{
    //如果大根堆中的完全二叉树为空树，则需要先给堆的完全二叉树的数组申请一个内存空间方便入堆一个新元素
    if (maxHeap->tree == NULL)
    {
        maxHeap->tree = (int*)malloc(sizeof(int));
        if (maxHeap->tree == NULL)
        {
            printf("内存不足！\n");
            return;
        }
        maxHeap->tree[0] = data;
        maxHeap->len++;//长度增加
        return;
    }
    //如果完全二叉树非空，则要先申请一段新的连续的内存空间（比之前的tree多一个内存空间）
    //然后将之前tree依次拷贝到新的内存空间中，并释放掉之前的tree
    //然后将新元素插入至tree数组的最末端
    int* q = (int*)malloc((maxHeap->len + 1) * sizeof(int));
    if (q == NULL)
    {
        printf("内存不足！\n");
        return;
    }
    //将元素依次拷贝到新空间
    for (int i = 0; i < maxHeap->len; i++)
    {
        q[i] = maxHeap->tree[i];
    }
    int* m = maxHeap->tree;
    maxHeap->tree = q;
    free(m);//释放掉旧的空间
    maxHeap->tree[maxHeap->len] = data;//将元素插入到最后一个空间中
    maxHeap->len++;//增加1个元素
    //parent对应的是父结点下标，最后一个元素的父结点是len/2向下取整
    int current = maxHeap->len - 1;//新入堆元素的下标
    //通过不断除2向下取整直到取整到0（根节点）结束来调整大根堆
    for (int parent = current / 2; parent >= 0; parent = parent / 2)
    {
        //如果当前元素大于父结点元素，则交换
        if (maxHeap->tree[current] > maxHeap->tree[parent])
        {
            swap(maxHeap->tree, current, parent);
            current = parent;//当前指针移动到父结点，准备下一次对比
        }
        else//如果不大于，就满足大根堆定义，直接跳出循环
        {
            break;
        }
    }
}

2.4 大根堆的删除操作

删除的时候要保证堆满足大根堆的定义，即双亲结点的值永远大于孩子结点的值，对于删除操作，先让堆底结点覆盖删除的元素，即用堆底结点换掉删除的结点（如果删除的是堆底结点，直接删除，什么都不影响），然后让这个覆盖后的新结点做调整，保证符合大根堆的定义，从其孩子结点入手，如果孩子结点比它大，则互换，并且让遍历的指针指向它和最大值的孩子互换后的它的位置，继续遍历做判断，直到这个堆满足大根堆的定义，根据这些性质，C语言实现的大根堆删除算法代码如下（详细思路见代码注释）：

//出大根堆（以出堆元素为根节点，找到其对应的子树，不断下沉，下沉过程中不断调整大根堆，达到出堆的效果）
//以完全二叉树层次遍历的顺序找到第一个值为elem的元素，并让其出大根堆
void popMaxHeap(MaxHeap* maxHeap,int elem)
{
    if (maxHeap->len == 0)
    {
        printf("堆空，不能出堆！\n");
        return;
    }
    int index = -1;//记录要出堆元素的下标，默认为-1（这样方便后续判断，因为数组下标不可能为-1）
    //找元素，确定其下标
    for (int i = 0; i < maxHeap->len; i++)
    {
        if (maxHeap->tree[i] == elem)
        {
            index = i;
            break;
        }
    }
    //如果没找到，提示并推出
    if (index == -1)
    {
        printf("没有找到值为%d的元素，无法删除！\n", elem);
        return;
    }
    //让堆底的元素占用覆盖被删除的元素的位置
    maxHeap->tree[index] = maxHeap->tree[maxHeap->len - 1];
    //准备一片新的内存空间，该空间比之前tree对应的内存空间少1个内存单元
    int* q = (int*)malloc((int)(maxHeap->len - 1) * sizeof(int));
    if (q == NULL)
    {
        printf("内存不足！\n");
        return;
    }
    //把元素都拷贝到新空间里（因为少了一个内存单元）
    for (int i = 0; i < maxHeap->len - 1; i++)
    {
        q[i] = maxHeap->tree[i];
    }
    //释放旧的内存空间
    int* m = maxHeap->tree;
    maxHeap->tree = q;
    free(m);
    maxHeap->len--;//删除了一个元素，堆长度减少1
    //找到了，开始删除操作，已知二叉树结点的下标为i，则其左孩子的下标为2*i+1，右孩子的下标为2*i+1+1=2*i+2（下标不是序号）
    //每次先从该结点的左孩子入手判断，如果左右孩子中右孩子大，那就让child++，使得其指向该结点的右孩子
    for (int child = 2 * index + 1; child < maxHeap->len; child = 2 * child + 1)
    {
        //先判断左右孩子哪个比较大，child是左孩子，child+1是右孩子（还需要判断当前节点是否是分支结点）
        if (child < maxHeap->len && maxHeap->tree[child] < maxHeap->tree[child + 1])
        {
            //那就让当前child指针指向较大的有孩子
            child++;
        }
        //如果左右孩子中最大的都没有覆盖要删除结点内存空间的结点的值大，则直接跳出循环不用换了，满足大根堆定义
        if (maxHeap->tree[index] > maxHeap->tree[child])
        {
            break;
        }
        else//否则，需要调换当前结点和最大的孩子结点的位置，并且让index指向那个其孩子（也就是曾经的根，它换到最大孩子的位置了）
        {
            swap(maxHeap->tree, index, child);
            index = child;
        }
    }
}

3. 堆排序（以大根堆为例）

堆排序是将一组序列视为完全二叉树的顺序存储的数组，然后将其进行调整大根堆，每次将根与未调整的最后一个元素（堆底）进行互换，然后再按大根堆的定义调整，加入最后一次调整好的是i，则堆底是i-1，这样排序出来的数组就是一个升序排列的数组，借助堆这个数据结构可以很快地完成排序，堆排序的平均时间复杂度为 $O(nlog_{2}{n})$ ，最坏时间复杂度是 $O(nlog_{2}{n})$ ，空间复杂度为 $O (1)$ 。*

P.S 堆排序是不稳定的，比如序列为1 ， 2， 2（#），#代表的是本来排在后面的2，经过堆排序后，序列变成了1,2（#）,2，造成原本后面的2跑到了前面，这就是不稳定的排序算法。*

3.1 调整大根堆

下面的算法是将下标从root到end的完全二叉树数列进行调整，使其满足大根堆定义（注意观察注释中说明的该算法和大根堆删除算法中循环遍历条件的不同，我在写这个算法的时候，出现了一点小问题：不进行最后一次调整，就是这个遍历条件导致的。），C语言实现调整大根堆算法如下：

//调整大根堆（从子树的根节点开始到最后一个分支结点结束）
void adjustMaxHeap(int* tree, int root, int end)
{
    //此处和出堆算法不同，出堆算法的child要小于堆的长度-1（下标和序号相差1，最后一个结点的序号是maxHeap->len），所以写小于maxHeap->len
    //而此处的end表示的是去除调整好元素后前面未调整元素的堆底的下标，所以要小于等于，下标和序号是有区别的
    for (int child = 2 * root + 1; child <= end; child = 2 * child + 1)
    {
        //先判断左右孩子哪个比较大，child是左孩子，child+1是右孩子（还需要判断当前节点是否是分支结点）
        if (child < end && tree[child] < tree[child + 1])//小根堆只需要将此行代码不等式条件改为小于即可
        {
            //那就让当前child指针指向较大的有孩子
            child++;
        }
        //如果左右孩子中最大的都没有覆盖要删除结点内存空间的结点的值大，则直接跳出循环不用换了，满足大根堆定义
        if (tree[root] > tree[child])//小根堆只需要将此行代码不等式条件改为大于即可
        {
            break;
        }
        else//否则，需要调换当前结点和最大的孩子结点的位置，并且让root指向那个其孩子（也就是曾经的根，它换到最大孩子的位置了）
        {
            swap(tree, root, child);
            root = child;
        }
    }
}

3.2 大根堆排序

//大根堆排序
void MaxHeapSort(int* arr,int n)
{
    //建立大根堆，从最后一个分支结点遍历到根节点
    for (int i = (n - 1) / 2; i >= 0; i--)
    {
        adjustMaxHeap(arr, i, n-1);
    }
    //根结点和待排序结点互换，待排序结点的前面的所有结点做调整
    int tmp=0;
    for (int i = n-1; i >0; i--)
    {
        swap(arr, i, 0);
        adjustMaxHeap(arr, 0, i-1);
    }
}

4. 完整的测试代码

#include <stdio.h>
#include<stdlib.h>
//交换数组中的下标为i和j对应的元素的位置
void swap(int* arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
//大根堆数据结构（一个用一维数组构建的完全二叉树），根结点大，孩子结点都比根结点小
typedef struct MaxHeap {
    int len;//堆长度
    int* tree;//存储完全二叉树的数组
}MaxHeap;
//初始化一个大根堆
MaxHeap* newMaxHeap()
{
    //最开始堆中无元素，所以堆长度为0，堆中的完全二叉树为空树
    MaxHeap* p = (MaxHeap*)malloc(sizeof(MaxHeap));
    if (p == NULL)
    {
        return NULL;
    }
    p->len = 0;
    p->tree = NULL;
    return p;
}
//入大根堆（堆的插入操作）
void pushMaxHeap(MaxHeap* maxHeap, int data)
{
    //如果大根堆中的完全二叉树为空树，则需要先给堆的完全二叉树的数组申请一个内存空间方便入堆一个新元素
    if (maxHeap->tree == NULL)
    {
        maxHeap->tree = (int*)malloc(sizeof(int));
        if (maxHeap->tree == NULL)
        {
            printf("内存不足！\n");
            return;
        }
        maxHeap->tree[0] = data;
        maxHeap->len++;//长度增加
        return;
    }
    //如果完全二叉树非空，则要先申请一段新的连续的内存空间（比之前的tree多一个内存空间）
    //然后将之前tree依次拷贝到新的内存空间中，并释放掉之前的tree
    //然后将新元素插入至tree数组的最末端
    int* q = (int*)malloc((maxHeap->len + 1) * sizeof(int));
    if (q == NULL)
    {
        printf("内存不足！\n");
        return;
    }
    //将元素依次拷贝到新空间
    for (int i = 0; i < maxHeap->len; i++)
    {
        q[i] = maxHeap->tree[i];
    }
    int* m = maxHeap->tree;
    maxHeap->tree = q;
    free(m);//释放掉旧的空间
    maxHeap->tree[maxHeap->len] = data;//将元素插入到最后一个空间中
    maxHeap->len++;//增加1个元素
    //parent对应的是父结点下标，最后一个元素的父结点是len/2向下取整
    int current = maxHeap->len - 1;//新入堆元素的下标
    //通过不断除2向下取整直到取整到0（根节点）结束来调整大根堆
    for (int parent = current / 2; parent >= 0; parent = parent / 2)
    {
        //如果当前元素大于父结点元素，则交换
        if (maxHeap->tree[current] > maxHeap->tree[parent])
        {
            swap(maxHeap->tree, current, parent);
            current = parent;//当前指针移动到父结点，准备下一次对比
        }
        else//如果不大于，就满足大根堆定义，直接跳出循环
        {
            break;
        }
    }
}
//出大根堆（以出堆元素为根节点，找到其对应的子树，不断下沉，下沉过程中不断调整大根堆，达到出堆的效果）
//以完全二叉树层次遍历的顺序找到第一个值为elem的元素，并让其出大根堆
void popMaxHeap(MaxHeap* maxHeap,int elem)
{
    if (maxHeap->len == 0)
    {
        printf("堆空，不能出堆！\n");
        return;
    }
    int index = -1;//记录要出堆元素的下标，默认为-1（这样方便后续判断，因为数组下标不可能为-1）
    //找元素，确定其下标
    for (int i = 0; i < maxHeap->len; i++)
    {
        if (maxHeap->tree[i] == elem)
        {
            index = i;
            break;
        }
    }
    //如果没找到，提示并推出
    if (index == -1)
    {
        printf("没有找到值为%d的元素，无法删除！\n", elem);
        return;
    }
    //让堆底的元素占用覆盖被删除的元素的位置
    maxHeap->tree[index] = maxHeap->tree[maxHeap->len - 1];
    //准备一片新的内存空间，该空间比之前tree对应的内存空间少1个内存单元
    int* q = (int*)malloc((int)(maxHeap->len - 1) * sizeof(int));
    if (q == NULL)
    {
        printf("内存不足！\n");
        return;
    }
    //把元素都拷贝到新空间里（因为少了一个内存单元）
    for (int i = 0; i < maxHeap->len - 1; i++)
    {
        q[i] = maxHeap->tree[i];
    }
    //释放旧的内存空间
    int* m = maxHeap->tree;
    maxHeap->tree = q;
    free(m);
    maxHeap->len--;//删除了一个元素，堆长度减少1
    //找到了，开始删除操作，已知二叉树结点的下标为i，则其左孩子的下标为2*i+1，右孩子的下标为2*i+1+1=2*i+2（下标不是序号）
    //每次先从该结点的左孩子入手判断，如果左右孩子中右孩子大，那就让child++，使得其指向该结点的右孩子
    for (int child = 2 * index + 1; child < maxHeap->len; child = 2 * child + 1)
    {
        //先判断左右孩子哪个比较大，child是左孩子，child+1是右孩子（还需要判断当前节点是否是分支结点）
        if (child < maxHeap->len && maxHeap->tree[child] < maxHeap->tree[child + 1])
        {
            //那就让当前child指针指向较大的有孩子
            child++;
        }
        //如果左右孩子中最大的都没有覆盖要删除结点内存空间的结点的值大，则直接跳出循环不用换了，满足大根堆定义
        if (maxHeap->tree[index] > maxHeap->tree[child])
        {
            break;
        }
        else//否则，需要调换当前结点和最大的孩子结点的位置，并且让index指向那个其孩子（也就是曾经的根，它换到最大孩子的位置了）
        {
            swap(maxHeap->tree, index, child);
            index = child;
        }
    }
}
//调整大根堆（从子树的根节点开始到最后一个分支结点结束）
void adjustMaxHeap(int* tree, int root, int end)
{
    //此处和出堆算法不同，出堆算法的child要小于堆的长度-1（下标和序号相差1，最后一个结点的序号是maxHeap->len），所以写小于maxHeap->len
    //而此处的end表示的是去除调整好元素后前面未调整元素的堆底的下标，所以要小于等于，下标和序号是有区别的
    for (int child = 2 * root + 1; child <= end; child = 2 * child + 1)
    {
        //先判断左右孩子哪个比较大，child是左孩子，child+1是右孩子（还需要判断当前节点是否是分支结点）
        if (child < end && tree[child] < tree[child + 1])//小根堆只需要将此行代码不等式条件改为小于即可
        {
            //那就让当前child指针指向较大的有孩子
            child++;
        }
        //如果左右孩子中最大的都没有覆盖要删除结点内存空间的结点的值大，则直接跳出循环不用换了，满足大根堆定义
        if (tree[root] > tree[child])//小根堆只需要将此行代码不等式条件改为大于即可
        {
            break;
        }
        else//否则，需要调换当前结点和最大的孩子结点的位置，并且让root指向那个其孩子（也就是曾经的根，它换到最大孩子的位置了）
        {
            swap(tree, root, child);
            root = child;
        }
    }
}
//大根堆排序
void MaxHeapSort(int* arr,int n)
{
    //建立大根堆，从最后一个分支结点遍历到根节点
    for (int i = (n - 1) / 2; i >= 0; i--)
    {
        adjustMaxHeap(arr, i, n-1);
    }
    //根结点和待排序结点互换，待排序结点的前面的所有结点做调整
    int tmp=0;
    for (int i = n-1; i >0; i--)
    {
        swap(arr, i, 0);
        adjustMaxHeap(arr, 0, i-1);
    }
}
//打印大根堆（按完全二叉树次序依次输出）
void printMaxHeap(MaxHeap* maxHeap)
{
    for (int i = 0; i < maxHeap->len; i++)
    {
        printf("%d\t", maxHeap->tree[i]);
    }
    printf("\n");
}

int main()
{
    MaxHeap* maxHeap = newMaxHeap();
    pushMaxHeap(maxHeap, 94);
    pushMaxHeap(maxHeap, 70);
    pushMaxHeap(maxHeap, 17);
    pushMaxHeap(maxHeap, 46);
    pushMaxHeap(maxHeap, 55);
    pushMaxHeap(maxHeap, 5);
    pushMaxHeap(maxHeap, 13);
    pushMaxHeap(maxHeap, 42);
    printf("大根堆插入结果：\n");
    printMaxHeap(maxHeap);
    popMaxHeap(maxHeap, 17);
    printf("大根堆删除元素15的结果：\n");
    printMaxHeap(maxHeap);
    int a[8] = { 94,70,17,46,55,5,13,42 };
    printf("待排序序列：\n");
    for (int i = 0; i < 8; i++)
    {
        printf("%d\t", a[i]);
    }
    printf("\n");
    MaxHeapSort(a, 8);
    printf("大根堆排序后的序列：\n");
    for (int i = 0; i < 8; i++)
    {
        printf("%d\t", a[i]);
    }
    printf("\n");
}