【算法与数据结构】深入解析二叉树（二）之堆结构实现

2024-03-16 09:04
文章标签 算法 二叉树 实现 数据结构 深入 解析 结构 之堆

本文主要是介绍【算法与数据结构】深入解析二叉树（二）之堆结构实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

请添加图片描述

文章目录

  • 📝二叉树的顺序结构及实现
    • 🌠 二叉树的顺序结构
    • 🌠 堆的实现
    • 🌠 堆的实现
      • 🌉堆向下调整算法
      • 🌉堆的创建
      • 🌉建堆时间复杂度
      • 🌉堆的插入
      • 🌉堆的删除
    • 🌠堆向上调整算法
      • 🌉堆的接口
    • 🌠堆的实现
    • 🌠堆的实现代码测试
  • 🚩总结

📝二叉树的顺序结构及实现

🌠 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述

🌠 堆的实现

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。 堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(且)或者(), ()
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
在这里插入图片描述

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等
堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

🌠 堆的实现

🌉堆向下调整算法

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

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

在这里插入图片描述

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

🌉堆的创建

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

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

在这里插入图片描述

代码：

int size=sizeof(array)/sizeof(int);
//向下建堆，复杂度为O(N)
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(array, size,i);
}
void AdjustDown(HPDataType* a, int n, int parent)
{ //a是数组指针,n是数组长度,parent是当前需要下调的父结点索引int child = parent * 2 + 1;//child表示父结点parent的左孩子结点索引,因为是完全二叉堆,可以通过parent和2计算得到while (child < n){//如果左孩子存在if (child + 1 < n && a[child + 1] < a[child]){//如果右孩子也存在,并且右孩子值小于左孩子,则child指向右孩子child++;}if (a[child] < a[parent])//如果孩子结点值小于父结点值,则需要交换{Swap(&a[child], &a[parent]);//交换孩子和父结点parent = child;//父结点下移为当前孩子结点child = parent * 2 + 1;//重新计算新的左孩子结点索引}else{break;}}
}

这是向下调整，最终形成小根堆，如果你想修改大根堆只需改变两个代码方向即可：

if (child+1<n && a[child + 1]>a[child])
if (a[child] > a[parent])

🌉建堆时间复杂度

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

复杂度：O(N)
在这里插入图片描述

🌉堆的插入

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

在这里插入图片描述

void HPPush(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);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

🌉堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

//时间复杂度是：logN
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

🌠堆向上调整算法

堆向上调整算法主要用于堆排序中,删除堆顶元素后,将最后一个元素补至堆顶,然后需要向上调整。

//向上调整，建堆O(N*logN)
for (int i = 1; i < size; i++)
{ //for循环从索引1开始,到size结束,即从第二个元素开始。AdjustUp(array, i);
}
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//计算父节点的位置:父节点位置 = (当前节点位置-1)/2while (child > 0)//如果当前节点位置大于0,并且当前节点值小于父节点值,需要向上调整:{if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}//将当前节点位置设为父节点的位置,重复执行步骤2和步骤3//直到当前节点位置为0,或者当前节点值不小于父节点值为止。else{break;}}
}

堆向上调整的主要步骤:：确定需要调整的子节点,通常是补至堆顶的最后一个元素。
时间复杂度为O(N*logN)
在这里插入图片描述

🌉堆的接口

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void Swap(int* px, int* py);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);//堆的简单初始化
//void HPInit(HP* php);
//堆的初始化+建堆
void HPInitArray(HP* php, HPDataType* a, int n);
//堆的销毁
void HPDestroy(HP* php);
//堆插入数据然后保持数据是堆
void HPPush(HP* php, HPDataType x);
//取堆顶的数据
HPDataType HPTop(HP* php);
//删除堆数据
void HPPop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HPEmpty(HP* php);

🌠堆的实现

#include"HeadSort.h"
//堆的简单初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HPInitArray(HP* php, HPDataType* a, int n)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");return;}memcpy(php->a, a, sizeof(HPDataType) * n);php->capacity = php->size = n;//HPInitArray:/*初始化堆数组,并将数据拷贝过来有两种方式建堆:向上调整:每个节点都与父节点比较,时间复杂度O(NlogN)向下调整:从最后一个非叶子节点开	始,每个节点与子节点比较,时间复杂度O(N)这里采用向下建堆,复杂度更低*///向上调整，建堆O(N*logN)/*for (int i = 1; i < php->size; i++){AdjustUp(php->a, i);}*///向下建堆，复杂度为O(N)for (int i = (php->size - 1 - 1) / 2; i >= 0; i--){AdjustDown(php->a, php->size,i);}
}void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}void Swap(int* px, int* py)
{int temp = *px;*px = *py;*py = temp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void HPPush(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);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}HPDataType HPTop(HP* php)
{assert(php);return php->a[0];}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child+1<n && a[child + 1]<a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//时间复杂度是：logN
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

🌠堆的实现代码测试

int main()
{int a[] = { 60,70,65,50,32,100 };HP hp;HPInitArray(&hp, a, sizeof(a) / sizeof(int));/*HPInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){                         HPPush(&hp, a[i]);}printf("%d\n", HPTop(&hp));HPPop(&hp);printf("%d\n", HPTop(&hp));*/while (!HPEmpty(&hp)){printf("%d\n", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);return 0;
}

在这里插入图片描述

🚩总结

感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘

请添加图片描述

这篇关于【算法与数据结构】深入解析二叉树（二）之堆结构实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/814980。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2