朋友们大家好啊,本篇文章来到堆的内容,堆是一种完全二叉树,再介绍堆之前,我们首先对树进行讲解
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合,n=0时成为空树,当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
这两种情况就是错误的
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图所示,这棵树结点的度的最大值是结点D的度为3,所以树的度为3
结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。
结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第L层,则其子树的根就在第L+1层。其双亲在同一层的结点互为堂兄弟。显然 D、E、F是堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度,当前树的深度为4。
提到存储结构,我们会想到两种:顺序存储和链式存储 先来看看顺序存储结构,用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的
树中某个结点的孩子可以有多个,这就意味着,无论按何种顺序将树中所有结点存储到数组中,结点的存储位置都无法直接反映逻辑关系,你想想看,数据元素挨个的存储,谁是谁的双亲,谁是谁的孩子呢?简单的顺序存储结构是不能满足树的实现要求的。
树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法
任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。
其中data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储地址。
typedef int DataType;
struct Node
{
struct Node* firstchild; // 第一个孩子结点
struct Node* rightsib; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
二叉树(Binary Tree)是n(n≥0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树具有五种基本情况:
完全二叉树的特点:
完全二叉树的性质
对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有: 5. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点 6. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子 7. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
前面我们已经谈到了树的存储结构,并且谈到顺序存储对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树,由于它的特殊性,使得用顺序存储结构也可以实现。 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系等
将这棵二叉树存入到数组中,相应的下标对应其同样的位置
考虑一种极端的情况,一棵深度为k的右斜树,它只有k个结点,却需要分配2k一1个存储单元空间,这显然是对存储空间的浪费,如图:
所以,顺序存储结构一般只用于完全二叉树
堆是一棵完全二叉树,堆中的每一个节点都满足堆性质,也就是每个节点的值都必须大于(或等于)或小于(或等于)其子节点的值。根据这个性质,堆可以分为两种类型:
下面是一个小堆的结构:
1
/ \
3 6
/ \ / \
5 9 8 13
在这个小堆中:
这个小堆对应数组存储结构为1 3 6 5 9 8 13
下面是一个大堆的结构:
13
/ \
9 8
/ \ / \
5 3 6 1
对应数组结构为13 9 8 5 3 6 1
堆的树形结构只是一种抽象的概念,在实际的物理存储上,堆通常是以数组的形式来实现的
堆的成立是数组数据不断调整的过程,这里我们创建出堆的框架:
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
初始化
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
初始化堆数据数组的指针为 NULL。这意味着堆开始时没有分配任何内存用于存储元素。通常,在第一次向堆中添加元素时,程序会根据需要分配内存
销毁
void HeapDestroy(Heap* php)
{
assert(php);
free(php->a);
php->size = 0;
php->capacity = 0;
}
free 函数释放堆结构中动态分配的数组 a 所占用的内存。php->a 是指向堆中元素数组的指针,在堆初始化或元素添加过程中,会通过 malloc、realloc 等动态内存分配函数分配内存。释放这块内存是防止内存泄露的重要步骤。释放后,这块内存不应再被访问
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->capacity = newcapacity;
php->a = tmp;
}
php->a[php->size] = x;
php->size++;
Ajustup(php->a, php->size - 1);
}
首先判断php不为空,再进行扩容,这个扩容在前面有多次提到 最主要的是下面的Ajustup函数
我们这里以小堆为例进行讲解:
当向堆中插入一个新元素后,为了维持小顶堆的性质(即父节点的值始终小于等于其子节点的值),可能需要进行元素的向上调整)。下面详细说明这个过程:
接下来我们用函数实现
void Ajustup(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 = (parent - 1) / 2;
}
else
break;
}
}
补充Swap函数:
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
有了这个调整函数,我们就可以建堆了
通过调用Ajustup函数,逐步把输入数组a转换成一个小堆
我们在主函数中进行测试
这个经验证确实是一个小堆
堆默认规定,要删除根节点的数据
堆顶存放最小值,删除后,为了满足小堆的性质,接下来根节点存储的为次小值
void HeapPop(Heap* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
Ajustdown(php->a,php->size,0);
}
向下调整函数
void Ajustdown(HPDataType* 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 = child * 2 + 1;
}
else
{
break;
}
}
}
我们需要找小一点的孩子进行交换
对于每次AdjustDown调用,最坏情况下需要进行的比较和交换次数与堆的高度成正比,即O(log n)
AdjustDown操作的时间复杂度是O(log n)
HPDataType HeapTop(Heap* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
如果是空,返回true,不是则返回false
本节内容到此结束,感谢大家观看!!!