光明网站建设,mip网站设计,公司员工培训方案,网络营销的特点包括哪些文章目录 前言堆的概念及结构堆的实现堆的向下调整算法#xff08;建小堆为例#xff09;堆的向上调整算法#xff08;建小堆为例#xff09;堆的初始化销毁堆堆的插入堆的删除(规定删堆顶的数据)取堆顶元素判断堆是否为空获取堆的个数 完整代码#xff08;包括测试代码建小堆为例堆的向上调整算法建小堆为例堆的初始化销毁堆堆的插入堆的删除(规定删堆顶的数据)取堆顶元素判断堆是否为空获取堆的个数 完整代码包括测试代码Heap.hHeap.ctest.c 前言
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。在现实中我们通常把堆 (一种完全二叉树) 使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
堆的概念及结构 【大根堆和小根堆】
根结点最大的堆叫做大根堆树中所有父亲都大于或等于孩子。
根结点最小的堆叫做小根堆树中所有父亲都小于或等于孩子。
堆的实现
首先新建一个工程
Heap.h堆的类型定义、接口函数声明、引用的头文件 Heap.c堆接口函数的实现 test.c主函数、测试栈各个接口功能
完整的代码放在后面包括测试代码这里就不会展示测试的效果图。大家可以自己别敲边按测试代码测试。图解会写的很详细的么么
堆的向下调整算法建小堆为例
现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提左右子树必须是一个堆才能调整。 int arr[] {27,15,19,18,28,34,65,49,25,37};
思想 1.选出左右孩子较小的一个值 2.然后和父亲进行比较如果比父亲小就进行交换并将原来小的孩子的位置当成父亲继续向下进行调整直到调整到叶子结点为止。如果比父亲大则停止向下调整此时该树就成小堆。
//交换函数
void Swap(HDataType* p1, HDataType* p2)
{HDataType tmp *p1;*p1 *p2;*p2 tmp;}//向下调整算法
void AdjustDown(HDataType* 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;}}}堆的向上调整算法建小堆为例
当我们在一个堆的末尾插入一个数据后需要对堆进行调整使其仍然是一个堆这时需要用到堆的向上调整算法。 假设在这个堆int arr[] {15,18,19,25,28,34,65,49,27,37}的末尾插入16.
思想 1.将要插入孩子的值与父亲的值比较。 2.若插入孩子的值比父亲的值小则交换插入孩子的值与父亲的值并将父亲的位置当作新的插入孩子的值继续进行向上调整。若插入孩子的值比父亲的值大则停止向上调整此时该树就成小堆。 //交换函数
void Swap(HDataType* p1, HDataType* p2)
{HDataType tmp *p1;*p1 *p2;*p2 tmp;}//向上调整算法
void AdjustUp(HDataType* 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;}}
}堆的初始化
//初始化堆
void HPInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}销毁堆
//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}堆的插入
数据插入时是插入到数组的末尾即树形结构的最后一层的最后一个结点所以插入数据后我们需要运用堆的向上调整算法对堆进行调整使其在插入数据后仍然保持堆的结构。
//堆的插入
void HPPush(HP* php, HDataType x)
{assert(php);//检查空间是否足够插入不够则扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HDataType* tmp (HDataType*)realloc(php-a, sizeof(HDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}//插入元素php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);// 从插入的元素开始进行向上调整保持它依然是堆
}堆的删除(规定删堆顶的数据)
堆的删除删除的是堆顶的元素但是这个删除过程可并不是直接删除堆顶的数据 1.将堆顶的数据与最后一个结点的数据交换 2.删除堆种最后一个元素此时左子树和右子树还是小堆 3.再对堆进行向下调整
//堆的删除(规定删堆顶的数据)
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);// 从根节点开始对剩下元素进行向下调整成大堆保持它依然是堆
}取堆顶元素
//取堆顶元素
HDataType HPTop(HP* php)
{assert(php);assert(php-size 0);//确保堆里有数据return php-a[0];//返回堆顶数据
}判断堆是否为空
//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;//判断堆中数据是否为0
}获取堆的个数
//获取堆的个数
int HPSize(HP* php)
{assert(php);return php-size;//返回堆中数据个数
}完整代码包括测试代码
Heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HDataType;
typedef struct Heap
{HDataType* a;int size;int capacity;}HP;//交换函数
void Swap(HDataType* p1, HDataType* p2);
//向上调整算法
void AdjustUp(HDataType* a, int child);
//向下调整算法
void AdjustDown(HDataType* a, int size, int parent);//初始化堆
void HPInit(HP* php);
//销毁堆
void PHDestroy(HP* php);
//堆的插入
void HPPush(HP* php, HDataType x);
//堆的删除(规定删堆顶的数据)
void HPPop(HP* php);
//取堆顶元素
HDataType HPTop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
//获取堆的个数
int HPSize(HP* php);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.h//小堆
void Swap(HDataType* p1, HDataType* p2)
{HDataType tmp *p1;*p1 *p2;*p2 tmp;}//向下调整算法
void AdjustDown(HDataType* 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;}}}
//向上调整算法
void AdjustUp(HDataType* 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;}}}
//初始化堆
void HPInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;}//堆的插入
void HPPush(HP* php, HDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HDataType* tmp (HDataType*)realloc(php-a, sizeof(HDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}//堆的删除(规定删堆顶的数据)
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);
}//取堆顶元素
HDataType HPTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}
//获取堆的个数
int HPSize(HP* php)
{assert(php);return php-size;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.hint main()
{int a[] { 4,3,7,9,1,5,8,2,8 };int sz sizeof(a) / sizeof(a[0]);HP hp;HPInit(hp);for (int i 0; i sz; i){HPPush(hp, a[i]);}//int k 5;//while (k--)//{// printf(%d\n, HPTop(hp));// HPPop(hp);//}while (!HPEmpty(hp)){printf(%d , HPTop(hp));HPPop(hp);}printf(\n);return 0;
}
