0
0

“堆的增删查改“以及“堆排序“详解

堆的增删查改:

堆的逻辑结构是完全二叉树，完全二叉树特点是最底层的节点连续，所以物理结构用数组构建。

给出结构体Heap(堆)，包含一个数组a，节点个数size(就是数据个数)，还有数组大小capacity。随后在Test.c文件中定义出这个结构体 HP hp；这里就按建小堆为例(小根堆:父亲小于等于孩子) 接下来我们来逐个分析如何构建堆相关的函数：

1.void HeapInit(HP* php); 初始化函数：

因为底层的物理结构就是数组，没什么好说的，把数组置空，size和capacity给成0就初始化完成。 

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

2.void HeapPush(HP* php, HPDataType x); 堆添加数据函数：

像这种添加数据的函数上来肯定要判断数组是否满：首先如果是空数组，就让 newcapacity 给成0，不满就给他php->capacity 的2倍，等会扩容完再把newcapacity 给capacity ，然后为了防止扩容失败 就先给a扩容完先赋给一个中间值tmp，判断如果tmp不是NULL扩容成功再给a。

判空结束后就要把值放进数组，放完以后因为要建小堆(建成下面图的样子)，就要利用向上调整法来建小堆，下面介绍 AdjustUp 函数

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 = (HPDataType*)realloc(php->a,sizeof(HPDataType)* newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a,php->size-1);
}

(2)void AdjustUp(HPDataType* a, size_t child) 向上调整函数：

假如已有下面的小堆，当最后添加0这个数据时，如何让它回到堆顶？只需找到他的父亲，孩子和父亲比较，如果孩子更小就交换，再刷新child和parent 直到child为0结束**(看下面动图解析)**，如果孩子比父亲大，因为要建大堆，那就不用再调整了，直接break

动图过程：(单纯的交换和刷新child和parent)

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])        //小堆
        {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

3.void HeapPop(HP* php) 堆顶删除函数：

先把堆顶和堆尾数据交换，把堆尾数据删除，再对新的堆进行向下调整法排成小堆，下面介绍 AdjustDown 函数

void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);            //忘写了！！！！！！！4
    swap(&php->a[php->size - 1], &php->a[0]);
    php->size--;
    AdjustDown(php->a,php->size,0);
}

(2) void AdjustDown(HPDataType* a, size_t size, int parent) 向下调整函数(向下调整法建小堆的前提是：务必保证左右子树都是小堆，如果建大堆就要保证左右子树都是大堆)：

当交换了堆顶和堆尾数据后是这个样子：

删除队尾数据，开始向下调整法：先从堆顶开始，通过 child=parent2+1 找出他的左右孩子中较小的那个和自己比 (先默认左孩子是较小孩子，比较左右孩子，如果右孩子小，就把右孩子赋给child )，如果较小的孩子比父亲小，就交换父亲和孩子，再刷新父亲孩子所指向的对象：新的parent 就是原本的child，新的child就是 新的parent 的孩子。如果建小堆 父亲比较小的孩子还小，那就不用再调整了，直接break，再重复循环进行，直到 child<size 不成立结束。(这里还有一点需要注意，如果当循环到最后一个父亲时，如果这个父亲只有左孩子没有右孩子，那么选较小孩子时，比较左右孩子就会越界访问，因此在选较小孩子时条件 要判断右孩子坐标是否小于总节点数，如果超出就没必要比较了，不超出才比较) ** 整个过程看下面动图！！！*

void AdjustDown(HPDataType* a, size_t size, int parent)
{
    size_t child = parent * 2 + 1;                //size_t!!!!!!!没写对2

    while (child < size)
    {    //默认左孩子是较小孩子，比较左右孩子，如果右孩子小，就把右赋给child
        if (child + 1 < size && a[child + 1] < a[child]) //小堆//size_t!!!!!!!位置放错了，放while外面了
        {
            child++;
        }
        //if (a[child] > a[parent])
        if (a[child] < a[parent])        //小堆
        {
            swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

向下调整动图：

( AdjustDown_better 就是调整为大堆而已，变了个 > )

4.剩下的HeapSize HeapTop HeapEmpty 都和顺序表的一个做法。

① size_t HeapSize(HP* php) 找堆大小函数：返回php->size 即可

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

② HPDataType HeapTop(HP* php) 找堆顶数据函数：保证堆不空的情况下返回php->a[0] 即可


HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);        //容易忘写！！！！！！！！！
    return php->a[0];
}

③ bool HeapEmpty(HP* php) 判断堆是否为空函数：判断php->size 是否为0，为0 空就返回true，不是0 非空就返回false 。

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

堆排序的两种做法：

①堆排序是什么？

通过堆操作把数组排成有序数组。

②为什么要有堆排序？

因为普通遍历排序时间复杂度是O(N²)，效率低，堆排序优于直接选择排序，才有价值，建堆的时间复杂度是O(N) (我的下一篇博客会讲解——详解堆排序的时间复杂度)

前提：

void test2()
{
    int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
    int size = sizeof(a) / sizeof(a[0]);
    HeapSort(a, size);
    int i = 0;
    for (i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
}
int main()
{
    test2();
    return 0;
}

1.void HeapSort(int a[],int size) 堆排序函数第一种写法：

自己创建一个堆hp，通过堆添加函数把数组a中的数据一个一个按小堆添加到 堆hp的数组hp->a 中，添加完的堆是小堆，再把堆顶数据赋给 数组a 后,调用堆顶删除函数 删掉堆顶数据，删完后依旧是小堆排列，再重复操作，直到堆为空结束，此时数组a中的数据就是从小到大排列。

void HeapSort(int a[],int size)
{
    HP hp;
    HeapInit(&hp);
    int i = 0;
    for (i = 0; i < size; i++)
    {
        HeapPush(&hp, a[i]);
    }
    HeapPrint(&hp);
    int j = 0;
    while (!HeapEmpty(&hp))
    {
        a[j++] = HeapTop(&hp);
        HeapPop(&hp);
    }
}

2.void HeapSort2(int a[],int size) 堆排序函数第二种写法：

如何把乱序的数组排成大堆：(建大堆)

从乱序的数组a的最后一个父亲(倒数第一个非叶子节点)开始进行向下调整法把这个父亲下面的分支排成大堆( 排升序为什么不是建小堆我在下一篇会重点讲，这里一知半解说不清楚 )，因为倒数第一个非叶子节点下面就是叶子了，满足左右子树为大堆的前提，所以一定可以调成大堆， 再让 父亲-- ，因为前面的操作已经使得下面的子树都排成大堆了，所以可以继续利用向下调整法把从这个父亲开始的整个树排成大堆，重复进行，直到父亲小于0结束。

void HeapSort2(int a[], int size)
{
    int i = 0;
    int end = size - 1;
    for (i = (end - 1) / 2; i >= 0; i--)
    {
        AdjustDown_better(a, size, i);
    }
    while (end > 0)
    {
        swap(&a[0], &a[end]);
        AdjustDown_better(a, end--, 0);
    }
}

举个例子：下面乱序的堆，只要按序号依次进行向下调整，就能逐个建成大堆，直到堆顶最后一次向下调整结束，父亲 i 小于0，结束，就建成了大堆

最后再依次交换队头队尾数据，再排出队尾数据，整体进行向下调整成大堆，(这里end=size-1，所以第一次就不用 -- ，)把大的数据依次放在队尾，最后end到第一个数据就没必要交换了，结束就是排升序。

下面是堆增删查改和堆排序的代码实现：

Heap.h

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

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

void HeapInit(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
void HeapPrint(HP* php);
bool HeapEmpty(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
void HeapDestroy(HP* php);
void swap(HPDataType* pa, HPDataType* pb);
void AdjustUp(HPDataType* a, size_t child);
void AdjustDown(HPDataType* a, size_t size, int parent);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"

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

void HeapPrint(HP* php)
{
    assert(php);
    int i = 0;
    int j = 0;
    int a = 1;
    for (i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
        if (i == j)
        {
            printf("\n");
            j +=pow(2,a++);            //!!!!!!!!!!看答案了1
        }
    }
    printf("\n\n");
}

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])        //小堆
        {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

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 = (HPDataType*)realloc(php->a,sizeof(HPDataType)* newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\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, int parent)
{
    size_t child = parent * 2 + 1;                //size_t!!!!!!!没写对2

    while (child < size)
    {
        if (child + 1 < size && a[child + 1] < a[child]) //小堆//size_t!!!!!!!位置放错了，放while外面了3
        {
            child++;
        }
        //if (a[child] > a[parent])
        if (a[child] < a[parent])        //小堆
        {
            swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void AdjustDown_better(HPDataType* a, size_t size, int parent)
{
    size_t child = parent * 2 + 1;                //size_t!!!!!!!没写对2

    while (child < size)
    {
        if (child + 1 < size && a[child + 1] > a[child]) //size_t!!!!!!!位置放错了，放while外面了3
        {
            child++;
        }
        if (a[child] > a[parent])        //大堆
        {
            swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);            //忘写了！！！！！！！4
    swap(&php->a[php->size - 1], &php->a[0]);
    php->size--;
    AdjustDown(php->a,php->size,0);
}

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

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

HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);        //忘写了！！！！！！！！！5
    return php->a[0];
}

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

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"

void TestHeap()
{
    HP hp;
    HeapInit(&hp);
    HeapPush(&hp, 1);
    HeapPush(&hp, 5);
    HeapPush(&hp, 0);
    HeapPush(&hp, 8);
    HeapPush(&hp, 3);
    HeapPush(&hp, 9);
    HeapPrint(&hp);

    HeapPop(&hp);
    HeapPrint(&hp);

    if (HeapEmpty(&hp))
    {
        printf("空\n");
    }
    else
    {
        printf("不空\n");
    }
    printf("%d\n", HeapSize(&hp));
    printf("%d\n", HeapTop(&hp));
    HeapDestroy(&hp);
}

void HeapSort(int a[],int size)
{
    HP hp;
    HeapInit(&hp);
    int i = 0;
    for (i = 0; i < size; i++)
    {
        HeapPush(&hp, a[i]);
    }
    HeapPrint(&hp);
    int j = 0;
    while (!HeapEmpty(&hp))
    {
        a[j++] = HeapTop(&hp);
        HeapPop(&hp);
    }

    //while (hp.size > 0)
    //{
    //    swap(&hp.a[0], &hp.a[hp.size - 1]);
    //    hp.size--;
    //    AdjustDown(hp.a, hp.size, 0);
    //}
    //for (i = 0; i < size; i++)
    //{
    //    a[i] = hp.a[i];
    //}
}

void HeapSort2(int a[], int size)
{
    int i = 0;
    int end = size - 1;
    for (i = (end - 1) / 2; i >= 0; i--)
    {
        AdjustDown_better(a, size, i);
    }
    while (end > 0)
    {
        swap(&a[0], &a[end]);
        AdjustDown_better(a, end--, 0);
    }
}

void test2()
{
    int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
    int size = sizeof(a) / sizeof(a[0]);
    HeapSort2(a, size);
    int i = 0;
    for (i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
}

int main()
{
    //TestHeap();
    test2();
    return 0;
}

运行结果：

① TestHeap

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

“&ldquo;堆的增删查改&ldquo;以及&ldquo;堆排序&ldquo;详解”的评论:

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

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

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

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

单元测试数据库回滚问题

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

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

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

文章导航