100.【C语言】数据结构之二叉树的堆实现(顺序结构) 1

目录

1.顺序结构

2.示意图

 ​编辑

从物理结构还原为逻辑结构的方法

3.父子节点编号的规律

4.顺序存储的前提条件

5.堆的简介

堆的定义

堆的两个重要性质

小根堆和大根堆 

6.堆的插入

7.堆的实现及操作堆的函数

堆的结构体定义

堆初始化函数HeapInit

堆插入元素函数HeapPush

堆向上调整函数AdjustUp

写法1

写法2

写法3

提问

向上调整的前提

测试堆插入函数

---

1.顺序结构

存储二叉树的两种结构:一种顺序结构,一种链式结构本文讲顺序结构

---

2.示意图

 

上方图中的数字0~6代表各个节点的编号 

逻辑结构:方便人理解的结构 物理结构:实实在在存储的结构

可见顺序结构的底层是用数组(连续)存储的

从物理结构还原为逻辑结构的方法

对于满二叉树而言,

第一层有一个节点,第二层有两个节点,第一层有四个节点......

则可按层拆分

再组合

加上线

 对于完全二叉树而言,做法和上述类似,不再赘述

3.父子节点编号的规律

比如求F的父节点,如果画图则太慢,其实可以看出规律

F编号为5,其父节点C编号为2;E编号为4,其父节点B编号为1;

发现(注:为高斯函数,又称向下取整函数)

★★★求父节点b编号的公式:

在C语言中为father = (child-1)/2;father获得表达式的商

如果给出父节点的编号,求左孩子和右孩子的编号

父节点C编号为2,则左孩子F的编号为2*2+1,则右孩子G的编号为2*2+2

★★★求孩子节点编号的公式:左孩子:  右孩子:

4.顺序存储的前提条件

结论:完全二叉树(含满二叉树)适合用顺序存储

如果非完全二叉树,存储会浪费空间

5.堆的简介

堆的定义

如果有一个关键码的集合，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： 且 且 (i=0,1,2,3,..,n)则称为小堆(或大堆)

堆的两个重要性质

• 堆中某个结点的值总是不大于或不小于其父结点的值；

• 堆总是一棵完全二叉树

小根堆和大根堆 

小根堆:树中所有的父节点的值都小于或等于孩子节点的值

大根堆:树中所有的父节点的值都大于或等于孩子节点的值

如果树中所有的父节点的值都等于孩子节点的值,则既为小根堆又为大根堆

注:等定义中并没有规定左孩子和右节点的值的大小关系,因此堆不一定有序

6.堆的插入

由堆的简介可知:堆是一个完全二叉树,因此可以用顺序结构实现

以下方大根堆为例

现要尾插数字20,由存储结构可以看出:空间不够,要扩容

插入20前,找其父节点(),发现后者值为30,可以插入,仍然满足大根堆的性质 

再尾插入60

发现不满足大根堆的性质,需要一次调整

发现调整后仍然不满足大根堆的性质(56<60),需要再一次调整 

发现调整后满足大根堆的性质(56<60<70),结束

上述的调整起名为向上调整,最多调整h(二叉树的高度)次

7.堆的实现及操作堆的函数

以大根堆为例

堆的结构体定义

可以用结构体来定义堆,由于堆的底层是用数组存储的,因此三个成员变量:数据域,大小size,容量capacity

写入头文件中

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

堆初始化函数HeapInit

要想使用堆必须先初始化堆(malloc,对size和capacity初始化值)

void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc");return;}php->size = 0;php->capacity = 4;
}

php->capacity跟随malloc函数开辟空间的大小

堆插入元素函数HeapPush

插入前先判断空间是否充足,不够则relloc原来的2倍.之后调用向上调整函数进行插入

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("realloc");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;//插入至数组的最后一个元素的下一个位置(size)php->size++;//数组大小+1//调用向上调整函数AdjustUp(php->a,php->size-1);
}

注意到AdjustUp传的第二个参数是php->size-1

堆向上调整函数AdjustUp

如果a[parent] < a[child],则进行交换,之后调整parent和child的值,以便于下一次调整

写法1

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (a[parent] < a[child]){Swap(&a[parent], &a[child]);//调整parent和child的值child = parent;parent = (parent - 1) / 2;}
}

写法2

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

写法3

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

提问

已知这几种写法都能成功运行,哪个写法存在不规范的地方?

答:从特殊情况考虑问题,写法2:

当parent==0时,进入循环,若child==1,if判断成立,交换值后,child==0,parent==-1/2==0(取商)

while(parent>=0)条件仍然成立,但不满足if (a[child] > a[parent]),因此break

不规范的地方:child==parent==0就没有必要再次进入循环,建议改成while (child>0)(写法3)

向上调整的前提

除了child位置,前面的数据结构构成堆

测试堆插入函数

main.c手动写入插入一些随机值,以下代码,下断点至return 0;

#include "Heap.h"
int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 1);HeapPush(&hp, 3);HeapPush(&hp, 0);HeapPush(&hp, 5);HeapPush(&hp, 8);HeapPush(&hp, 12);HeapPush(&hp, 2);HeapPush(&hp, 5);HeapPush(&hp, 30);HeapPush(&hp, 50);return 0;}

打开监视窗口查看

画图后发现符合大根堆的性质