[数据结构]——二叉树——堆的实现

1. 堆的概念及结构

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，
2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

2. 堆的实现

1.堆的创建


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

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

2. 建堆时间复杂度


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

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

3.堆的插入


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

 4.堆的删除


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

 5.堆向下调整算法

                                                                                                


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

 3.代码深度解析

1.首先弄一个交换数据

 交换两个指针所指向的变量的值

通过解引用操作符*，将p2指针所指向的变量的值赋给了p1指针所指向的变量，将之前存储在temp中的值赋给了p2指针所指向的变量，完成了交换。

void Swap(HPDataType *p1, HPDataType *p2)
{
    HPDataType temp = *p1;
    *p1 =*p2;
    *p2 = temp;
}

2.向上调整堆

将数组a中指定索引child的元素向上调整，使其在最小堆中满足最小堆的性质

通过计算child的父节点索引，即(parent = (child - 1) / 2)，确定了父节点的位置。在循环中，child的元素比父节点的元素小调用Swap函数，将child和parent指向的元素进行交换。然后，代码更新child和parent的值，将child变为parent，parent变为(child - 1) / 2，继续循环。如果不是，即child的元素不小于父节点的元素，代码通过break语句跳出循环，这时已经完成了向上调整的操作。

void AdjudtUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

3.向下调整堆

调整小顶堆的算法，接受一个int类型的指针a，表示一个数组，size表示数组的大小， parent表示要调整的节点位置

void AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

4.堆的插入

堆已满，则需要扩容。然后，将原来的内存空间指针hp->_a指向新分配的内存空间，更新堆的容量为新的容量。将要插入的元素x赋值给堆的最后一个位置hp->_a[hp->_size]，然后增加堆的大小hp->_size++。最后，调用AdjustUp函数将新插入的元素向上调整，以维护堆的性质

void HeapPush(Heap* hp, HPDataType  x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)
    {
        int newCapacity = hp->_capacity == 0 ? 4: hp->_capacity * 2;
        HPDataType*temp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType));
        if (temp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a =temp;
        hp->_capacity = newCapacity;
    } 
    hp->_a[hp->_size] = x;
    hp->_size++;
    AdjudtUp(hp->_a,hp->_size-1);
}

5.堆的创建

初始化后再通过for循环遍历数组a，并调用HeapPush函数将数组中的元素依次插入到堆中

void HeapCreate(Heap* hp, HPDataType *a, int n )
{
    assert(hp);
    hp->_size = 0; 
    hp->_capacity =NULL; 

    // 将数组a中的元素依次插入堆中
    for (int i = 0; i < n; i++) {
        HeapPush(hp, a[i]);
    }
}

6.堆的销毁

使用free函数释放堆的数组hp->_a的内存空间

void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_size =hp->_capacity=0;

}

7.堆的删除

调用AdjustDown()函数，从堆顶开始向下调整堆，以保持堆的性质

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}

8.取堆顶的数据


函数返回堆中数组_a的第一个元素即堆顶的数据

取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    return hp->_a[0];
}

9.堆的数据个数

返回堆的_size成员，即堆的大小

int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}



10. 堆的判空

  1. 通过断言assert(hp);来确保传入的参数hp不为NULL。

  2. 然后，通过判断堆的大小hp->_size是否为0来判断堆是否为空。

  3. 如果堆的大小为0，则返回1（即堆为空），否则返回0（即堆不为空）

int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}

4.总的代码

1.heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
//数据交换
void Swap(HPDataType* p1, HPDataType* p2);
//向上堆的调整
void AdjudtUp(Heap* _a, int child);
// 向下调整堆
void AdjustDown(int* a, int size, int parent);
// 堆的构建
//void HeapCreate(Heap* hp);//, HPDataType* a, int n
 void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

2.Heap.c

#include"Heap.h"
//交换数据
void Swap(HPDataType *p1, HPDataType *p2)
{
    HPDataType temp = *p1;
    *p1 =*p2;
    *p2 = temp;
}
//向上调整堆
void AdjudtUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
// 向下调整堆
void AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType  x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)
    {
        int newCapacity = hp->_capacity == 0 ? 4: hp->_capacity * 2;
        HPDataType*temp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType));
        if (temp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a =temp;
        hp->_capacity = newCapacity;
    } 
    hp->_a[hp->_size] = x;
    hp->_size++;
    AdjudtUp(hp->_a,hp->_size-1);
}
// 堆的构建
//void HeapCreate(Heap* hp)//HPDataType* a, int n
//{
//    assert(hp);
//    hp->_size = 0; // 初始化堆的大小为0
//    hp->_capacity = 0; // 设置堆的容量为n
//    hp->_a = NULL;
//
//     将数组a中的元素依次插入堆中
//    //for (int i = 0; i < n; i++) {
//    //    HeapPush(&hp, a[i]);
//    //}
//}
void HeapCreate(Heap* hp, HPDataType *a, int n )
{
    assert(hp);
    hp->_size = 0; // 初始化堆的大小为0
    hp->_capacity =NULL; // 
    hp->_a = NULL;

    // 将数组a中的元素依次插入堆中
    for (int i = 0; i < n; i++) {
        HeapPush(hp, a[i]);
    }
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_size =hp->_capacity=0;

}
// 堆的删除
void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}

2.Test.c

#include"Heap.h"
void test()                          
{
	Heap sl;
	int a[10] = { 10,8,2,4,5,3,6,7,9,1 };
	/*HeapCreate(&sl);
	for (int i = 0;i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&sl, a[i]);
	}*/
	HeapCreate(&sl,a, sizeof(a) / sizeof(int));
	while (!HeapEmpty(&sl))	{
		printf("%d  ", HeapTop(&sl));
		HeapPop(&sl);
	}
	printf("\n");
}
int main()
{
	test();
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/547812.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【力扣TOP100热题图解】T1.两数之和

【力扣TOP100热题图解】T1.两数之和

题目链接点这里—— 力扣&#xff08;LeetCode&#xff09;​​​​​​ 法一&#xff1a;暴力枚举 最容易想到的方法是枚举数组中的每一个数 x&#xff0c;寻找数组中是否存在 target - x。 当我们使用遍历整个数组的方式寻找 target - x 时&#xff0c;需要注意到每一个位…
阅读更多...
ViT——nlp和cv进行了统一，使多模态成为可能

ViT——nlp和cv进行了统一，使多模态成为可能

题目：AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE 1.概述之前的transformer在cv中应用，大部分是将CNN模型中部分替换成transformer block（整体网络结构不变）或者用transformer将不同网络连接起来，而本文提出：一个针对图像patch的纯的t…
阅读更多...
雷达智能名片小程序源码系统 带完整的安装代码包以及搭建教程

雷达智能名片小程序源码系统 带完整的安装代码包以及搭建教程

在数字化高速发展的今天&#xff0c;名片作为商务交流中的一张“金名片”&#xff0c;其形式与功能也在不断地迭代升级。雷达智能名片小程序源码系统应运而生&#xff0c;为企业和个人提供了一个全新的、智能化的名片展示与互动平台。本文将对雷达智能名片小程序源码系统的开发…
阅读更多...
二叉树的前、中、后序遍历【c++】

二叉树的前、中、后序遍历【c++】

前序遍历&#xff1a;根左右 中序遍历&#xff1a;左根右 后序遍历&#xff1a;左右根 #include <iostream> #include <vector> using namespace std;//双链表节点结构 typedef struct treeNode {int value;struct treeNode* left;struct treeNode* right;treeNod…
阅读更多...
【python】在pycharm用Django写一个API接口

【python】在pycharm用Django写一个API接口

背景 Django是一个高级的Python Web框架&#xff0c;它鼓励快速开发和干净、实用的设计。它由经验丰富的开发者设计&#xff0c;解决了Web开发的大部分麻烦&#xff0c;因此开发者可以专注于编写应用而不是重复造轮子。Django遵循MVC设计模式&#xff0c;并拥有自带的一套便捷…
阅读更多...
Testng测试框架（2）-测试用例@Test

Testng测试框架（2）-测试用例@Test

测试方法用 Test 进行注释&#xff0c;将类或方法标记为测试的一部分。 Test() public void aFastTest() {System.out.println("Fast test"); }import org.testng.annotations.Test;public class TestExample {Test(description "测试用例1")public void…
阅读更多...
【Unity 实用工具篇】 | UIEffect 实现一系列UGUI特效，灰度、负片、像素化特效

【Unity 实用工具篇】 | UIEffect 实现一系列UGUI特效，灰度、负片、像素化特效

前言 【Unity 实用工具篇】 | UIEffect 实现一系列UGUI特效&#xff0c;灰度、负片、像素化特效一、UGUI特效插件&#xff1a;UIEffect1.1 介绍1.2 效果展示1.3 使用说明及下载 二、组件属性面板三、代码操作组件四、组件常用方法示例4.1 使用灰度特效做头像(关卡)选择 总结 前…
阅读更多...
C语言实现三子棋游戏（可以改变为四子棋或者多子棋版）

C语言实现三子棋游戏（可以改变为四子棋或者多子棋版）

游戏介绍 三子棋游戏或者说是井字棋游戏&#xff0c;相信大家都玩过&#xff0c;一般的流程就是在一个棋盘上&#xff0c;玩家下棋之后&#xff0c;电脑下棋&#xff0c;然后判断输赢&#xff0c;如果没输没赢&#xff0c;就再玩家下棋&#xff0c;电脑下棋。 游戏框架 对于…
阅读更多...
AI大模型探索之路-应用篇13：企业AI大模型选型指南

AI大模型探索之路-应用篇13：企业AI大模型选型指南

目录 前言 一、概述 二、有哪些主流模型&#xff1f; 三、模型参数怎么选&#xff1f; 四、参数有什么作用&#xff1f; 五、CPU和GPU怎么选&#xff1f; 六、GPU和显卡有什么关系&#xff1f; 七、GPU主流厂商有哪些&#xff1f; 1、NVIDIA芯片怎么选&#xff1f; 2、…
阅读更多...
Web前端 Javascript笔记1

Web前端 Javascript笔记1

为什么学习 JavaScript? JavaScript 是 web 开发人员必须学习的 3 门语言中的一门&#xff1a; HTML 定义了网页的内容CSS 描述了网页的布局JavaScript 控制了网页的行为 JavaScript 是可插入 HTML 页面的编程代码。 JavaScript 插入 HTML 页面后&#xff0c;可由所有的现代浏…
阅读更多...
FPGA原理与结构（8）——块RAM（Block RAM,BRAM）

FPGA原理与结构（8）——块RAM（Block RAM,BRAM）

系列文章目录&#xff1a;FPGA原理与结构&#xff08;0&#xff09;——目录与传送门 一、BRAM简介 大家对于RAM应该并不陌生&#xff0c;RAM就是一张可读可写的存储表&#xff0c;它经常被拿来与ROM进行对比&#xff0c;相比之下&#xff0c;ROM只可读。而在FPGA中&#xff0c…
阅读更多...
图灵奖2023：Avi Wigderson的开创性贡献揭示计算中的随机性和伪随机性

图灵奖2023：Avi Wigderson的开创性贡献揭示计算中的随机性和伪随机性

文章目录 每日一句正能量前言背景什么是理论计算机科学&#xff1f;为什么随机性很重要&#xff1f;三篇影响深远的论文Avi Wigderson在计算复杂性理论方面的贡献及其对现代计算的影响Avi Wigderson对随机性和伪随机性在计算中作用的理解及其实际应用Avi Wigderson的学术生涯和…
阅读更多...
用于密集视觉冲击的紧凑三维高斯散射Compact 3D Gaussian Splatting For Dense Visual SLAM

用于密集视觉冲击的紧凑三维高斯散射Compact 3D Gaussian Splatting For Dense Visual SLAM

Compact 3D Gaussian Splatting For Dense Visual SLAM 用于密集视觉冲击的紧凑三维高斯散射 Tianchen Deng 邓天辰11Yaohui Chen 陈耀辉11Leyan Zhang 张乐妍11Jianfei Yang 杨健飞22Shenghai Yuan 圣海元22Danwei Wang 王丹伟22Weidong Chen 陈卫东11 Abstract 摘要 …
阅读更多...
008、Python+fastapi，第一个后台管理项目走向第8步：ubutun 20.04下安装vscode+python环境配置

008、Python+fastapi，第一个后台管理项目走向第8步：ubutun 20.04下安装vscode+python环境配置

一、说明 白飘了3个月无影云电脑&#xff0c;开始选了个windows server 非常不好用&#xff0c;后台改为ubuntu想升级到22&#xff0c;没成功&#xff0c;那就20.04吧。 今天先安装下开发环境&#xff0c;后续2个月就想把他当做开发服务器&#xff0c;不知道行不行&#xff0c;…
阅读更多...
行式存储VS列式存储对比

行式存储VS列式存储对比

行式存储&#xff1a; 一行代表一个记录的所有字段。 可以快速读取和写入单条记录。 如果要检索一条数据&#xff0c;数据库会读取or写入整条记录&#xff0c;包含所有相关字段。 列式存储&#xff1a; 表中每一列的数据连续存放。这种方式在需要对某一列进行大量运算或分析时…
阅读更多...
PSAvatar：一种基于点的可变形形状模型，用于3D高斯溅射的实时头部化身创建

PSAvatar：一种基于点的可变形形状模型，用于3D高斯溅射的实时头部化身创建

PSAvatar: A Point-based Morphable Shape Model for Real-Time Head Avatar Creation with 3D Gaussian Splatting PSAvatar&#xff1a;一种基于点的可变形形状模型&#xff0c;用于3D高斯溅射的实时头部化身创建 Zhongyuan Zhao1,2, Zhenyu Bao1,2, Qing Li1, Guoping Qiu3,…
阅读更多...
计算机虚拟机服务器中了mallox勒索病毒怎么办Mallox勒索病毒解密流程工具

计算机虚拟机服务器中了mallox勒索病毒怎么办Mallox勒索病毒解密流程工具

在当今社会&#xff0c;人们的工作生活离不开网络&#xff0c;尤其企业离不开网络办公&#xff0c;网络为企业提供了极大便利&#xff0c;大大提升了企业的生产效率与办公水平&#xff0c;但网络是一把双刃剑&#xff0c;在为企业提供便利的同时也为企业的数据带来严重威胁。近…
阅读更多...
【攻防世界】warmup

【攻防世界】warmup

[HCTF 2018]WarmUp全网最详细解释_[hctf 2018]warmup的解-CSDN博客 php://filter 读取源码&#xff08;文件&#xff09; php://input 执行php代码&#xff0c;需要post请求提交数据 Content-Type为image/jpeg text. 绕过后缀的有文件格式有php,php3,php4,php5,pht…
阅读更多...
探索企业级应用开发解决方案

探索企业级应用开发解决方案

1、什么是企业级应用 企业级应用是指为商业组织、大型企业创建并部署的应用。 企业级应用的结构复杂、涉及的外部资源众多、事务密集、数据量大、用户数多&#xff0c;需要较强的安全性。其特点有&#xff1a; &#xff08;1&#xff09;海量数据持久保存。 &#xff08;2&a…
阅读更多...
不出天府锋巢直播产业基地，即可激活电商直播产业、产教融合及人才培训服务

不出天府锋巢直播产业基地，即可激活电商直播产业、产教融合及人才培训服务

天府锋巢直播产业基地打造直播产业产教融合及人才培训服务新模式&#xff0c;携手政府、企业、高校&#xff0c;促进直播产业与创新人才双向奔赴&#xff0c;推进教学与实战深度融合&#xff0c;推动实习与就业无缝衔接。 各方资讯一应俱全 直播产业产教融合及人才培训服务全套…
阅读更多...
最新文章

Copyright @ 2022~2023