0
0

P8—＜堆及堆排序＞《数据结构(C语言版)》

《数据结构(C语言版)》实战项目之堆及堆排序的功能实现

                                                                          ——By 作者：新晓·故知

一、完整源码：

完整源码如下，欢迎复制测试指正！

堆及堆排序的功能实现测试示例：

调试测试：

完整源码：

Test.c:

#include"Heap.h"
//堆的实现
//这里采用小堆法

//堆的插入测试
void TestHeap1()
{
    HP hp;
    HeapInit(&hp);
    //1.一个一个创建数据(可随机，可乱序）
    HeapPush(&hp, 7);
    HeapPush(&hp, 1);
    HeapPush(&hp, 5);
    HeapPush(&hp, 6);
    HeapPush(&hp, 4);
    HeapPush(&hp, 9);
    HeapPrint(&hp);

    2.使用循环创建数据（只能有序创建）
    //for (int i = 0; i < 5; i++)
    //{
    //    HeapPush(&hp, i);
    //}
    //HeapPrint(&hp);
    HeapDestroy(&hp);

}

//堆顶删除元素测试
void TestHeap2()
{
    HP hp;
    HeapInit(&hp);
    //1.一个一个创建数据(可随机，可乱序）
    HeapPush(&hp, 7);
    HeapPush(&hp, 1);
    HeapPush(&hp, 5);
    HeapPush(&hp, 6);
    HeapPush(&hp, 4);
    HeapPush(&hp, 9);
    HeapPrint(&hp);
    //删除堆顶元素
    HeapPop(&hp);
    HeapPrint(&hp);

}
//求堆大小测试
void TestHeap3()
{
    HP hp;
    HeapInit(&hp);
    //1.一个一个创建数据(可随机，可乱序）
    HeapPush(&hp, 7);
    HeapPush(&hp, 1);
    HeapPush(&hp, 5);
    HeapPush(&hp, 6);
    HeapPush(&hp, 4);
    HeapPush(&hp, 9);
    HeapPrint(&hp);

    int i=HeapSize(&hp);
    printf("%d ", i);
}

//取堆顶元素测试
void TestHeap4()
{
    HP hp;
    HeapInit(&hp);
    //1.一个一个创建数据(可随机，可乱序）
    HeapPush(&hp, 7);
    HeapPush(&hp, 1);
    HeapPush(&hp, 5);
    HeapPush(&hp, 6);
    HeapPush(&hp, 4);
    HeapPush(&hp, 9);
    HeapPrint(&hp);

    int i=HeapTop(&hp);
    printf("%d ", i);

}




//堆排序测试—（升序）
//如果（降序），只需更改Heap.c中的注释判断部分

//1.交换-删除-调整法:
//时间复杂度: O（N* logN)
//空间复杂度: O(N)

//优化：建堆    空间：O（1）

//2.覆盖法：
//时间复杂度： O（N^2)

堆排序-1
//时间复杂度: O（N* logN)
//空间复杂度: O(N)
//void HeapSort(int* a, int size)
//{
//    HP hp;
//    HeapInit(&hp);
//    //O（N* logN)
//    for (int i = 0; i < size; ++i)
//    {
//        HeapPush(&hp, a[i]);
//    }
//    //O（N* logN)
//    size_t j = 0;
//    while (!HeapEmpty(&hp))
//    {
//        a[j] = HeapTop(&hp);
//        j++;
//        HeapPop(&hp);
//    }
//
//    HeapDestroy(&hp);
//
//}


//建堆算法
//堆排序-1++  优化：建堆
//时间复杂度:O（N* logN)、
//空间复杂度:O（1）
//直接在原数组建堆
void HeapSort(int* a, int n)
{
    建堆1.——向上调整   时间复杂度:O（N* logN)
    //for (int i = 1; i < n;++i)
    //{
    //    AdjustUp(a, i);
    //}
    
    //建堆2.——向下调整     时间复杂度:O（N)
    //不能直接建堆，因为向下调整函数功能有要求
    //从倒数第一个非叶子结点（最后一个叶子结点的父亲）开始
    for (int i = (n - 1 - 1) / 2;i >= 0; --i)
    {
        AdjustDown(a, n, i);
    }

    //交换调整
    size_t end = n - 1;
    while (end>0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}

int main()
{
    //TestHeap1();
    //TestHeap2();
    //TestHeap3();
    //TestHeap4();

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

    for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

Heap.c:

#include"Heap.h"
//堆的实现
//这里采用小堆法
//堆的实现操纵的是数组，想象的是二叉树结构！！！
//堆的功能函数

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

//堆的打印
void HeapPrint(HP* php)
{
    assert(php);
    for (size_t i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}

//堆的销毁
void HeapDestroy(HP* php)
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}
//堆的交换
void Swap(HPDataType* pa, HPDataType* pb)
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
//堆的向上调整
void AdjustUp(HPDataType* a, size_t child)
{
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
        //小堆-升序
        //if (a[child] < a[parent]) 
        大堆-降序
        //if (a[child] > a[parent])
        //升序要建大堆（根据建堆分析）
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

//堆的插入（插入x以后，保持其依旧是小堆/大堆）
void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    if (php->size == php->capacity)
    {
        size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
        //HPDataType* tmp 这样做，如果relloc失败，不会将原来的空间覆盖为0
        //如果php->a最初为0，则相当于malloc
        //在栈的实现中没有这样做，栈的实现有缺陷，要注意！
        if (tmp == NULL)
        {
            printf("relloc falied\n");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }

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

    //向上调整，控制保持是一个小堆
    AdjustUp(php->a, php->size - 1);
}

//向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        //1.选出左右孩子中小的那个
        
        //小堆-升序
        //if (child + 1 < size && a[child +1] < a[child])
        //大堆-降序
        //if (child + 1 < size && a[child + 1] >a[child])
        //升序要建大堆（根据建堆分析）
        if (child + 1 < size && a[child + 1] >a[child])

        {
            ++child;
        }
        //2.如果孩子小于父亲，则交换，并继续向下调整
        
        //if (a[child] < a[parent])  //小堆-升序
        //if (a[child] > a[parent])  //大堆-降序
        //升序要建大堆（根据建堆分析）
        if (a[child] >a[parent])

        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//堆的删除（删除堆顶的数据，该数据是最小/最大）
void HeapPop(HP* php)
{
    assert(php);
    Swap(&php->a[0], &php->a[php->size - 1]);
    --php->size;

    //向下调整
    AdjustDown(php->a, php->size, 0);
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}
//求堆的大小
size_t HeapSize(HP* php)
{
    assert(php);

    return php->size;
}
//取堆顶
HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

Heap.h:

#pragma once
//堆的实现
//这里采用小堆法
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//堆的底层物理结构上是一个数组（动态增长），逻辑上是一个完全二叉树
//动态结构——方便（也可使用静态结构）
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    size_t size;
    size_t capacity;
}HP;

//堆的初始化
void HeapInit(HP* php);
//这个是将数组拷贝，使用建堆算法
//void HeapInitArray(HP* php, HPDataType*a,size_t n);

//堆的销毁
void HeapDestroy(HP* php);
//堆的插入（插入x以后，保持其依旧是小堆/大堆）
void HeapPush(HP* php, HPDataType x);
//堆的删除（删除堆顶的数据，该数据是最小/最大）
void HeapPop(HP* php);
//堆的交换
void Swap(HPDataType* pa, HPDataType* pb);
//堆的打印
void HeapPrint(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//求堆的大小
size_t HeapSize(HP* php);
//取堆顶
HPDataType HeapTop(HP* php);
//向上调整
void AdjustUp(HPDataType* a, size_t child);
//向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root);

二、堆及堆排序实现分析：

**1.堆的概念及结构 **

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

**2.堆的实现 **

**2.1 **堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[ ] = {27,15,19,18,28,34,65,49,25,37};

*2.2***堆的创建 **

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

**2.3 ****建堆时间复杂度 **

因为堆是完全二叉树,而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：*建堆的时间复杂度为***O(N)**。

**2.4 ****堆的插入 **

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

**2.5 ****堆的删除 **

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

**2.6 **堆的代码实现

（1）堆的初始化

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

（2）堆的打印

//堆的打印
void HeapPrint(HP* php)
{
    assert(php);
    for (size_t i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}

（3）堆的销毁

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

（4）堆的交换

//堆的交换
void Swap(HPDataType* pa, HPDataType* pb)
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

（5）堆的向上调整

//堆的向上调整
void AdjustUp(HPDataType* a, size_t child)
{
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
        //小堆-升序
        //if (a[child] < a[parent]) 
        大堆-降序
        //if (a[child] > a[parent])
        //升序要建大堆（根据建堆分析）
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

（6）堆的向下调整

//向下调整
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        //1.选出左右孩子中小的那个
        
        //小堆-升序
        //if (child + 1 < size && a[child +1] < a[child])
        //大堆-降序
        //if (child + 1 < size && a[child + 1] >a[child])
        //升序要建大堆（根据建堆分析）
        if (child + 1 < size && a[child + 1] >a[child])

        {
            ++child;
        }
        //2.如果孩子小于父亲，则交换，并继续向下调整
        
        //if (a[child] < a[parent])  //小堆-升序
        //if (a[child] > a[parent])  //大堆-降序
        //升序要建大堆（根据建堆分析）
        if (a[child] >a[parent])

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

（7）堆的插入

//堆的插入（插入x以后，保持其依旧是小堆/大堆）
void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    if (php->size == php->capacity)
    {
        size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
        //HPDataType* tmp 这样做，如果relloc失败，不会将原来的空间覆盖为0
        //如果php->a最初为0，则相当于malloc
        //在栈的实现中没有这样做，栈的实现有缺陷，要注意！
        if (tmp == NULL)
        {
            printf("relloc falied\n");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }

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

    //向上调整，控制保持是一个小堆
    AdjustUp(php->a, php->size - 1);
}

（8）堆的删除（堆顶元素）

//堆的删除（删除堆顶的数据，该数据是最小/最大）
void HeapPop(HP* php)
{
    assert(php);
    Swap(&php->a[0], &php->a[php->size - 1]);
    --php->size;

    //向下调整
    AdjustDown(php->a, php->size, 0);
}

（9）判断堆是否为空

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

    return php->size == 0;
}

（10）求堆的大小

//求堆的大小
size_t HeapSize(HP* php)
{
    assert(php);

    return php->size;
}

（11）取堆顶元素

//取堆顶
HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

**3. ****堆的应用 **

**3.1 **堆排序

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

  1. **建堆 **

    ★升序：建大堆 

★降序：建小堆

  2. **利用堆删除思想来进行排序 **

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

——By 作者：新晓·故知

标签： 数据结构
本文转载自: https://blog.csdn.net/m0_57859086/article/details/123946479
版权归原作者 新晓·故知 所有， 如有侵权，请联系我们删除。
登录后发布评论

“P8&mdash;＜堆及堆排序＞《数据结构(C语言版)》”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航