廊坊专业网站网站,200元网站建设,马鞍山网站开发,正规品牌网站设计图片引言
今天要讲的堆#xff0c;不是操作系统虚拟进程地址空间中#xff08;malloc#xff0c;realloc等开空间的位置#xff09;的那个堆#xff0c;而是数据结构中的堆#xff0c;它们虽然名字相同#xff0c;却是截然不同的两个概念。堆的底层其实是完全二叉树#x…引言
今天要讲的堆不是操作系统虚拟进程地址空间中mallocrealloc等开空间的位置的那个堆而是数据结构中的堆它们虽然名字相同却是截然不同的两个概念。堆的底层其实是完全二叉树如果你问我完全二叉树是什么。好吧那我先从树开始讲起开始我们今天的内容。
树是什么 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。 注意树形结构中子树之间不能有交集否则就不是树形结构。 上图的三个结构都不是树不符合子树之间无交集的定义子树相交其实就成了图。
关于树的常见概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6叶节点/终端节点度为0的节点称为叶节点 如上图B、C、H、I...等节点为叶节点非终端节点或分支节点度不为0的节点 如上图D、E、F、G...等节点为分支节点双亲节点/父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点孩子节点/子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点树的高度/深度树中节点的最大层次 如上图树的高度为4节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙。
以上是学习堆要了解的基本概念。
对于树结构的模拟
虽然树已经有了很多限制和规则但其还是有着很大的灵活性我们根据其结构特性也给出了一些定义方案。
1.如果明确了树的度那么可以定义TreeNode
typedef struct TreeNode
{int data;struct TreeNode* child1;struct TreeNode* child2;struct TreeNode* child3;//。。。
}TreeNode;
像上述代码中定义的那样可以固定定义一种固定度数的结点。
2.左孩子右兄弟表示法
struct Node
{int data;//结点中的数据struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点
};
实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 但我们用的正真多的是二叉树
二叉树是什么
二叉树的概念
二叉树是特殊的树
一棵二叉树是结点的一个有限集合该集合:
或者为空由一个根节点加上两棵别称为左子树和右子树的二叉树组成 上图中我们可以看出 1. 二叉树的度不大于2每个结点最多有两个孩子 2. 二叉树有左右之分次序不能颠倒因此二叉树是有序树 当然以下几种情况也符合二叉树的定义都是二叉树 二叉树的存储结构
二叉树一般可以使用两种存储结构一种是顺序结构一种链式结构。
1.顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储而这就引入到了我们今天要讲的堆。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2.链式存储
二叉树的链式存储结构是指用链来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面课程学到高阶数据结构如红黑树等会用到三叉链。 typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
特殊的二叉树
1. 满二叉树一个二叉树的每一层都是满的如果一个树的层数为K且结点数为2^k - 1则它就是满二叉树。
2.完全二叉树如一个树的深度为h前h-1层都是满的最后一层不满但连续。
下图中左边的是满二叉树右边的是完全二叉树 完全二叉树是一种效率很高的数据结构堆的逻辑结构实则就是一个完全二叉树。
二叉树顺序结构实现堆
普通的二叉树我们可以称为非完全二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。
如果强行用堆表示普通的二叉树就会像下面这样 如果用完全二叉树实现那么就是这样
现在应该能体会到两种实现的区别了吧 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 堆的概念及结构 堆的性质 一颗完全二叉树大堆树中任何一个父亲都大于等于孩子小堆树中任何一个父亲都小于等于孩子 在这个堆中如果你细心观察可以发现如下规律这个规律很重要 知道父亲下标parent找孩子child 左孩子下标leftchild parent * 2 1右孩子下标rightchild parent * 2 2 知道孩子下标child找父亲parent parent child - 1/ 2 用代码模拟堆的结构就是以下这样
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;//存放堆数据的数组int _size;//堆数据个数int _capacity;//堆的容量-可扩容
}Heap;
下面我们默认先建一个小堆后期如果需要改大堆只需要变动相应比较符号就可以
堆的插入
如果存在一个有十个元素的堆想要往其中插入一个新的元素其过程是下面这样 以下是插入部分的代码实现
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);//如果空间不够就扩容if (hp-_size hp-_capacity) {int newcapacity hp-_capacity 0 ? 4 : hp-_capacity * 2;HPDataType* tmp (HPDataType*)realloc(hp-_a, sizeof(HPDataType) * newcapacity);if (tmp NULL) {perror(realloc fail:);exit(1);}hp-_a tmp;hp-_capacity newcapacity;}hp-_a[hp-_size] x;hp-_size;//向上调整算法AdjustUp(hp-_a, hp-_size - 1);
}
在这里将新插入的10这个元素往上调整的过程我们称之为向上调整涉及到一个算法那就是向上调整算法现在我们来实现一份。
向上调整算法
在比较交换元素的过程中我们提供一个比较函数以便交换元素
//交换
void my_swap(HPDataType* a, HPDataType* b)
{int tmp *a;*a *b;*b tmp;
} 以下就是对向上调整的实现
//向上调整
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent (child - 1) / 2;//如果孩子为0则比较结束while (child 0) {if (a[parent] a[child]) {my_swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else break;}
}
找相比较的父子结点根据堆中父子结点位置规则先找到需要比较检查调整的父子结点比较父子结点大小如果建立小堆且子节点小于父节点交换父子结点数据如果此时子节点大于父节点跳出循环更新父子结点将父节点的位置赋给child同时更新parent检查是否退出循环如果child0时跳出循环
堆的创建
下面我们给出一个数组的元素建成一个堆。在刚刚讲完堆的插入和向上调整过后其实创建堆就显得格外容易了。我们只需要从数组中取出元素然后依次插入到堆中便可以完成堆的创建以下是实现代码
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{assert(hp);//初始化堆时别忘记初始化以下hp中的元素hp-_a NULL;hp-_capacity hp-_size 0;for (int i 0; i n; i) {HeapPush(hp, a[i]);AdjustUp(hp-_a, hp-_size - 1);}
}
堆的删除
堆的删除通常意义上是删除堆顶的元素。如果建的是小堆那么堆顶的元素就是堆中最小的数如果建的是大堆那么堆顶就是堆中最大的元素。
想要删除堆顶元素不能通过整体向前移动后面的堆元素的方式来删除元素因为这样会打乱元素之间的父子关系打乱了父子关系整个堆就很有可能不符合“父亲一定小于等于或大于等于孩子”这一规则了。
真正的实现方式是将堆顶元素和堆底元素互换位置将size - 1再将此时堆顶的元素进行向下调整。
过程见下图 // 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(hp-_size ! 0);my_swap(hp-_a[0], hp-_a[hp-_size - 1]);hp-_size--;//向下调整AdjustDown(hp-_a, hp-_size, 0);
}
既然讲到了向下调整其实就又涉及到了向下调整算法。
向下调整算法
向下调整顾名思义就是将元素往下调先给大家展示调整代码再来解析过程
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child parent * 2 1;while (child n) {if (child 1 n a[child 1] a[child]) {child;}if (a[parent] a[child]) {my_swap(a[parent], a[child]);parent child;child parent * 2 1;}else break;}
}
找相比较的父子结点根据堆中父子结点位置规则先找到需要比较检查调整的父子结点这里先预设左孩子比右孩子小当发现右孩子更小时child 1在比较左右孩子之前还需要考虑到child 1不会导致越界比较父子结点父节点大于子结点时此时建立的是小堆交换父子结点数据如果父节点小于字结点跳出循环更新父子结点将child赋给parent计算新的child进入新一轮循环判断循环结束当孩子跃出数据存储范围时循环结束
取堆顶的数据
这里没什么好说堆的数组中第一个元素就是堆顶的数据
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp-_size ! 0);return hp-_a[0];
}
堆数据的个数和堆的判空
这里直接用堆中的size元素就OK
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);return hp-_size 0;
}
堆的销毁
跟顺序表的销毁基本一致
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-_a);hp-_a NULL;hp-_capacity 0;hp-_size 0;
}
到这里堆的实现基本上就结束了
体验一下手写的堆
#includeheap.h
int main()
{Heap hp;int arr[] { 5,4,3,2,1 };HeapCreate(hp, arr, sizeof(arr) / sizeof(int));printf(%d\n\n, HeapSize(hp));while (!HeapEmpty(hp)) {printf(%d\n, HeapTop(hp));HeapPop(hp);}HeapDestory(hp);return 0;
} 结语
今天的内容到这里就结束了本篇博客带大家认识了一下树和堆但这里只是带大家稍微看了看堆的实现。关于堆的内容其实还有很多topk问题堆排序优先级队列中会更深入的带领大家去了解和使用堆在下一篇数据结构中会更深入的挖掘一些堆的应用并计算一下其时间复杂度让大家体会到堆的魅力。如果还想了解更多有趣的内容还请多多支持博主比心♥
