0
0

数据结构与算法-——堆

文章目录

堆的结构分析

需要注意的是堆是一种数据结构，与操作系统的堆区没有关系。

堆的结构：堆是完全二叉树，从左到右是连续的，适合用数组存储

在这里插入图片描述

在这里插入图片描述

堆是一颗完全二叉树，分为大堆和小堆

大堆：一个树中，任何父亲节点都大于等于孩子节点，所以大堆的根节点最大

小堆：一个树中，任何父亲节点都小于等于孩子节点，所以小堆的根节点最小

在这里插入图片描述

堆的实现

了解过顺序表的小伙伴，对堆的实现就非常简单了，采用malloc动态内存分配开辟空间存储节点。因为要满足大堆或小堆，需要用到向上调整和向下调整算法，我们直接在下面的实现中了解，先以大堆为例，到时候只需要微调向上调整和向下调整就能实现大堆与小堆的切换

堆的存储结构

typedef int HPDataType;

typedef struct Heap
{
    HPDataType* p;
    int size;//节点个数
    int capacity;//空间容量
}HP;

堆初始化

//对象传给HeapInit函数初始化
int mian()
{
    HP h;
    HeapInit(&h);
}

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

堆的插入push

建堆：为了不破坏堆的原有结构，就要依次尾插，而要满足大堆，每次插入就要与父亲节点比较大小，不断向上调整，最终实现大堆

int arr[6] = { 70, 56, 30, 60, 25, 40 };

向上调整

插入的节点不断与父亲节点比较，如果孩子节点大于父亲节点，就交换位置，然后再次与新的父亲节点比较，小于父亲节点就终止

在这里插入图片描述

//交换函数在下面的堆删除也能复用
void HeapSwap(HPDataType* p1, HPDataType* p2)
{    
    assert(p1 && p2);
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void AdjustUp(HPDataType* p, int child)
{    
    assert(p);
    int parent = (child - 1) / 2;
    while (child >0)
    {
        //大于父亲节点就调整
        if (p[child] > p[parent])
        {
            HeapSwap(&p[child], &p[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}
//插入节点也需要判断空间是否满了，满了就扩容
void HeapPush(HP* pc, HPDataType x)
{
    assert(pc);
    //扩容
    if (pc->capacity == pc->size)
    {
        int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(pc->p, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        pc->p = tmp;
        pc->capacity = newcapacity;
    }
    pc->p[pc->size] = x;
    pc->size++;
    AdjustUp(pc->p, pc->size-1);
}

堆判空

当我们需要删除堆中节点时，首先就需要判断堆是否为空，是否有节点存在，如同上面堆插入需要先判断空间是否满了

bool HeapEmpty(HP* pc)
{
    assert(pc);

    return pc->size == 0;
}

堆删除pop

堆的删除是头删，但如果直接删除堆顶元素，就会破坏堆的原有结构了，所以我们可以先交换堆顶与堆尾的元素再尾删，之后再向下调整

向下调整

向下调整：父亲节点与较大的孩子节点比较大小，如果小于孩子节点就向下调整，父亲节点大于等于较大的孩子节点就终止

在这里插入图片描述

在这里插入图片描述

通过上面的图发现：

父亲节点为0 左孩子1=0*2+1

​ 右孩子：2=0*2+2

父亲节点为1 左孩子：3=1*2+1

​ 右孩子：4=1*2+2

同时左孩子+1就是右孩子

所以leftchild=parent*2+1

​ rightchild=leftchild+1

同时paren=（child-1）/ 2 , child：左右孩子都行

父亲节点为0 左孩子1=0*2+1

​ 右孩子：2=0*2+2

父亲节点为1 左孩子：3=1*2+1

​ 右孩子：4=1*2+2

同时左孩子+1就是右孩子

所以leftchild=parent*2+1
​ rightchild=leftchild+1
同时paren=（child-1）/ 2 , child：左右孩子都行

AdjustDown(HPDataType* p, int n, int parent)
{    
    //左孩子
    int child = parent * 2 + 1;
    while (child < n)
    {    
        //判断是否有右孩子且右孩子大于左孩子
        if (child + 1 < n && p[child + 1] > p[child])
            ++child;
        if (p[child] < p[parent])
        {
            HeapSwap(&p[child], &p[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}
void HeapPop(HP* pc)
{
    assert(pc && !HeapEmpty(pc));

    HeapSwap(&pc->p[pc->size - 1], &pc->p[0]);
    pc->size--;
    AdjustDown(pc->p, pc->size, 0);
}

堆销毁

void HeapDestroy(HP* pc)
{    
    assert(pc && !HeapEmpty(pc));
    //释放动态开辟的空间
    free(pc->p);
    pc->capacity = pc->size = 0;
}

运行结果

将数组元素依次push形成的大堆

在这里插入图片描述

pop一次形成的大堆

在这里插入图片描述

大堆我们已经实现了，如果要换成小堆，就是父亲节点总是小于等于孩子节点

1、向上调整中，父亲节点>较小的孩子节点则交换

2、向下调整中，父亲节点>较小的孩子节点则交换

时间复杂度分析

对堆的时间复杂度分析，也就是向上调整和向下调整算法的时间复杂度，而它们的时间复杂度与树的高度有关
以向下调整为例：
假设树的高度为h：

第1层，20个节点，需要向下移动h-1层

第2层，21个节点，需要向下移动h-2层

第3层，22个节点，需要向下移动h-3层

第4层，23个节点，需要向下移动h-4层

……

第h层，2h-2个节点，需要向下移动h-4层

则需要移动节点的总步数为：

T(n)=20*(h-1)+21*(h-2)+22*(h-3)+23*(h-4)+2h-32+2h-21 1

2T(n)=21(h-1)+22*(h-2)+23*(h-3)+24*(h-4)+2h-22+2h-11 2

2-1错位相减：

T(n)=1-h+21+22+23+24+……+2h-2+2h-1

T(n)=20+21+22+23+24+2h-2+2h-1-h

T(n)=2h-1-h

n=2h-1 h=log2(n+1)

T(n)=n-log2(n+1) 约等n

源代码

Heap.h

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

typedef int HPDataType;

//实现大堆
typedef struct Heap
{
    HPDataType* p;
    int size;
    int capacity;
}HP;

//堆初始化
void HeapInit(HP* pc);
//堆中元素交换
void HeapSwap(HPDataType* p1, HPDataType* p2);
//打印元素
void HeapPrint(HP* pc);
//堆插入
void HeapPush(HP* pc, HPDataType x);
//堆删除
void HeapPop(HP* pc);
//堆销毁
void HeapDestroy(HP* pc);
//堆判空
bool HeapEmpty(HP* pc);
//向上调整
void AdjustUp(HPDataType* p, int child);
//向下调整
AdjustDown(HPDataType* p, int n, int parent);
//获取堆顶元素
HPDataType HeapTop(HP* pc);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

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

void HeapPrint(HP* pc)
{    
    assert(pc);
    for (int i = 0; i < pc->size; i++)
    {
        printf("%d ", pc->p[i]);
    }
    printf("\n");
}

void HeapSwap(HPDataType* p1, HPDataType* p2)
{    
    assert(p1 && p2);
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void AdjustUp(HPDataType* p, int child)
{    
    assert(p);
    int parent = (child - 1) / 2;
    while (child >0)
    {
        //大于父亲节点就调整
        if (p[child] > p[parent])
        {
            HeapSwap(&p[child], &p[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

void HeapPush(HP* pc, HPDataType x)
{
    assert(pc);
    //扩容
    if (pc->capacity == pc->size)
    {
        int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(pc->p, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        pc->p = tmp;
        pc->capacity = newcapacity;
    }
    pc->p[pc->size] = x;
    pc->size++;
    AdjustUp(pc->p, pc->size-1);
}

bool HeapEmpty(HP* pc)
{
    assert(pc);

    return pc->size == 0;
}

AdjustDown(HPDataType* p, int n, int parent)
{    
    //左孩子
    int child = parent * 2 + 1;
    while (child < n)
    {    
        //判断是否有右孩子且右孩子大于左孩子
        if (child + 1 < n && p[child + 1] > p[child])
            ++child;
        if (p[child] > p[parent])
        {
            HeapSwap(&p[child], &p[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}
void HeapPop(HP* pc)
{
    assert(pc && !HeapEmpty(pc));

    HeapSwap(&pc->p[pc->size - 1], &pc->p[0]);
    pc->size--;
    AdjustDown(pc->p, pc->size, 0);
}
HPDataType HeapTop(HP* pc)
{
    assert(pc && !HeapEmpty(pc));
    return pc->p[0];
}

void HeapDestroy(HP* pc)
{    
    assert(pc && !HeapEmpty(pc));
    
    free(pc->p);
    pc->capacity = pc->size = 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void Heap()
{
    int arr[6] = { 70, 56, 30, 60, 25, 40};
    HP h;
    HeapInit(&h);
    //将数组的元素依次插入堆
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    {
        HeapPush(&h, arr[i]);
    }
    HeapPrint(&h);

    HeapPop(&h);
    HeapPrint(&h);

    HeapDestroy(&h);
}
int main()
{    
    Heap();

    return 0;
}

堆的经典应用

1、Topk问题

2、堆排序

之后的文章会依次介绍，希望我的文章能对你有所帮助。欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏

在这里插入图片描述

标签： 数据结构 算法 c语言
本文转载自: https://blog.csdn.net/weixin_46016019/article/details/123030101
版权归原作者 寄一片海给你 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构与算法-&mdash;&mdash;堆”的评论:

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

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

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

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

单元测试数据库回滚问题

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

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

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

文章导航