甘肃省建设厅执业注册中心网站,网站维护更新,广州天河区是富人区吗,如何设置多个首页wordpress目录
前言
一种完全二叉树#xff1a;堆
堆的概念
堆的性质
建堆的时间复杂度
建堆的空间复杂度#xff1a;
小堆的实现
必要补充
堆的初始化
堆的销毁
向上调整算法
堆的插入
向下调整算法
堆的删除
获取堆顶元素
获取堆中元素个数
堆的判空
最终代码
He…目录
前言
一种完全二叉树堆
堆的概念
堆的性质
建堆的时间复杂度
建堆的空间复杂度
小堆的实现
必要补充
堆的初始化
堆的销毁
向上调整算法
堆的插入
向下调整算法
堆的删除
获取堆顶元素
获取堆中元素个数
堆的判空
最终代码
Heap.h文件
Heap.c文件
test.c文件
大堆的实现
思考堆的意义是什么
1、堆排序
2、top k问题 前言 在上一篇中我们学习了二叉树的基本概念C语言二叉树的基本概念一现在我们来学习一种完全二叉树堆以及大小堆的实现......
一种完全二叉树堆
堆的概念
概念如果有一个关键码的集合K { k0k1k2…}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中若分别满足以下两种情况则称该堆为小/大堆 根节点为最大值的堆叫做最大堆或大根堆根节点为最小值的堆叫做最小堆或小根堆 堆的性质
堆是一个完全二叉树堆中每一个节点的值都必须大于等于或小于等于其子树中每个节点的值
建堆的时间复杂度
1、我们将一个高度为h的满二叉树转变成一个小堆该小堆的结点总数为log(N1)
一般来说对数的底我们将其忽略所以这里原本是log(以2为底N1的对数) 第一层的结点个数为2^0、第二层的结点个数为2^1......第h层的结点个数为2^(h-1) 结点总数为2^0 2^1 ......2^(h-1) 2^h - 1 等比数列求和公式Sna1 (1-q^n)/ (1-q) 假设结点总数为N则N与h的关系是N 2^h - 1 h log(N1) 即一个高h的满二叉树的结点个数为log(N1) 2、进行堆的调整得到最终的时间复杂度为O(N*logN) 第一层元素向上调整0次第二层元素向上调整1次......第h层元素向上调整h-1次 同时每一层元素中的结点个数又分别为2^0、2^1......2^(h-1) 总调整次数T为T 2^0×0 2^1×1 ......2^(h-1)×(h-1) ① 利用错位相减法列出第二个式子2*T 2^1×0 2^2×1 ......2^h×(h-1) ② 由① - ②得 T 2 2^h * (h-2) ③ 将h log以2为底N1的对数代入③得④ T N1log以2为底N1的对数- 2 * N ④ 将④利用大O渐进表示法转换为 T(N) O(N*log以2为底N的对数) 结论建堆的时间复杂度为O(N*logN)
建堆的空间复杂度 小堆的空间复杂度为O(n)其中n是小堆中元素的个数。在建堆的过程中需要额外的空间来存储数组中的元素。
结论建堆的空间复杂度为O(N)
小堆的实现
我们利用顺序表顺序存储方式实现堆
必要补充
堆的任何一个父结点的编号parent与其左孩子结点的编号leftchild满足如下关系式: 理解这里是我们后续在编写向上调整算法与向下调整算法时的基础
堆的初始化
//初始化堆
void HeapInit(HP* php)
{//检查堆的有效性assetr(php);php-a NULL;php-capacity 0;php-size 0;}
堆的销毁
free可以用来检查是否为空若指针为空则free不执行任何操作指针不为空就释放内存空间
//堆的销毁
void HeapDestroy(HP* php)
{assert(php);//释放a指针的内存空间并将a指针置为空free(php-a);php-a NULL;php-capacity 0;php-size 0;
}
向上调整算法
//向上调整
void AdjustUP(HPDataType* a,int child)
{int parent (child - 1) / 2;//当孩子等于0的时候它已经位于树顶了没有父亲了就应该结束循环while(child 0){//if (a[child] a[parent])就是它if (a[child] a[parent]){//如果儿子小于父亲就交换父子位置同时将此时Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}//由于是写一个小堆所以当孩子大于等于父亲时不需要交换直接退出循环即可else{break;}}
} 堆的插入
//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){size_t newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc error);return -1;}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;//向上调整,从顺序表最后一个元素开始调整该元素的下标为size-1AdjustUP(php-a, php-size - 1);}
每插入一个新的元素都需要进行一次向上调整的判断
向下调整算法
//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{//根据之前的推论左孩子的下标值为父亲下标值的两倍1左孩子的下标值为父亲下标值的两倍2int child parent * 2 1;//循环结束的条件是走到叶子结点while (child size){//if (child 1 size a[child 1] a[child])它也是//假设左孩子小若假设失败则更新child转换为右孩子小同时保证child的下标不会越界if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){//如果此时满足孩子小于父亲则交换父子位置同时令父亲的下标变为此时的儿子所在下标儿子所在下标变为自己的儿子所在的下标向下递归Swap(a[child], a[parent]);parent child;child parent * 2 1;}//如果父亲小于等于左孩子就证明删除后形成的新堆是一个小堆不再需要向下调整算法循环结束else{break;}}
} 堆的删除
//堆的删除
void HeapPop(HP* php)
{assert(php);assert(php-size 0);//这里并不采用惯用的顺序表头删的办法向前覆盖因为那样会引起堆的顺序被完全打乱的问题我们在这里选择交换堆顶元素与堆尾元素然后再进行一次顺序表的尾删直接size--即可Swap(php-a[0], php-a[php-size - 1]);php-size--;//在交换完并尾删完后可能此时的堆并不能满足小堆的要求堆顶元素比它的两个孩子都大所以我们必须再次对堆进行调整经过向下调整算法将堆恢复至小堆由于是堆顶元素开始调整所以还需传入堆顶元素对应的下标0AdjustDown(php-a, php-size, 0);
} 每删除一个元素都需要进行一次向下调整的判断
获取堆顶元素
//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//获取堆顶元素则堆里应该有元素故首先要保证size不小于等于零assert(php-size 0);//确定堆中有元素后返回a[0]即可return php-a[0];
}获取堆中元素个数
//获取堆中元素个数
size_t HeapSize(HP* php)
{assert(php);//判断size大于零后返回size大小即可return php-size;
}堆的判空
//堆的判空
bool HeapEmpty(HP* php)
{assert(php);//返回对php-size 0的判断结果return php-size 0;
}
最终代码
Heap.h文件
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h#pragma once
typedef int HPDataType;
typedef struct Heap
{HPDataType* a; //指向存储元素的指针int capacity; //当前顺序表容量int size; //当前顺序表的长度
}HP;//初始化堆
void HeapInit(HP* php);//销毁堆
void HeapDestroy(HP* php);//向上调整算法
void AdjustUP(HPDataType* a, int child);//堆的插入
void HeapPush(HP* php,HPDataType x);//向下调整算法
void AdjustDown(HPDataType* a, int child);//堆的删除删除堆顶的数据
void HeapPop(HP* php);//获取堆顶元素
HPDataType HeapTop(HP* php);//获取堆中元素个数
size_t HeapSize(HP* php);//堆的判空
bool HeapEmpty(HP* php);
Heap.c文件
#include Heap.h//初始化堆
void HeapInit(HP* php)
{//检查堆的有效性assert(php);php-a NULL;php-size 0;php-capacity 0;
}//堆的销毁
void HeapDestroy(HP* php)
{assert(php);//释放a指针的内存空间并将a指针置为空free(php-a);php-a NULL;php-capacity 0;php-size 0;
}//交换父子位置
void Swap(HPDataType* p1,HPDataType* p2)
{HPDataType* tmp *p1;*p1 *p2;*p2 tmp;
} //向上调整此时传递过来的是最后一个孩子的元素下标我们用child表示
void AdjustUP(HPDataType* a,int child)
{//由于我们要调整父亲与孩子的位置所以此时也需要父亲元素的下标而0父亲元素的下标值 任意一个孩子的下标值-1/ 2 int parent (child - 1) / 2;//当孩子等于0的时位于树顶数组首元素的位置树顶元素没有父亲循环结束while(child 0){//如果孩子还未到顶且它的下标对应的元素值小于它的父亲的下标对应的元素值就将父子位置交换交换玩后还要将下标对应的值“向上移动”//if (a[child] a[parent])就是它if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}//由于这是一个小堆所以当孩子大于等于父亲时不需要交换直接退出循环即可else{break;}}
}//堆的插入
void HeapPush(HP* 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, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc error);return -1;}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;//向上调整,从顺序表最后一个元素开始调整该元素的下标为size-1AdjustUP(php-a, php-size-1);
}//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{//根据之前的推论左孩子的下标值为父亲下标值的两倍1左孩子的下标值为父亲下标值的两倍2int child parent * 2 1;//循环结束的条件是走到叶子结点while (child size){//假设左孩子小若假设失败则更新child转换为右孩子小同时保证child的下标不会越界//if (child 1 size a[child 1] a[child])它也是if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){//如果此时满足孩子小于父亲则交换父子位置同时令父亲的下标变为此时的儿子所在下标儿子所在下标变为自己的儿子所在的下标向下递归Swap(a[child], a[parent]);parent child;child parent * 2 1;}//如果父亲小于等于左孩子就证明删除后形成的新堆是一个小堆不再需要向下调整算法循环结束else{break;}}
}//堆的删除
void HeapPop(HP* php)
{assert(php);assert(php-size 0);//这里并不采用惯用的顺序表头删的办法向前覆盖因为那样会引起堆的顺序被完全打乱的问题我们在这里选择交换堆顶元素与堆尾元素然后再进行一次顺序表的尾删直接size--即可Swap(php-a[0], php-a[php-size - 1]);php-size--;//在交换完并尾删完后可能此时的堆并不能满足小堆的要求堆顶元素比它的两个孩子都大所以我们必须再次对堆进行调整经过向下调整算法将堆恢复至小堆由于是堆顶元素开始调整所以还需传入堆顶元素对应的下标0AdjustDown(php-a, php-size, 0);
}//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//获取堆顶元素则堆里应该有元素故首先要保证size不小于等于零assert(php-size 0);//确定堆中有元素后返回a[0]即可return php-a[0];
}//获取堆中元素个数
size_t HeapSize(HP* php)
{assert(php);//判断size大于零后返回size大小即可return php-size;
}//堆的判空
bool HeapEmpty(HP* php)
{assert(php);//返回对php-size 0的判断结果return php-size 0;
}
test.c文件
#include Heap.hint main()
{int arr[] { 4,6,2,1,5,8,2,9 };int sz sizeof(arr) / sizeof(arr[0]);HP hp;HeapInit(hp);for (int i 0;i sz; i){HeapPush(hp,arr[i]);}//堆不为空就获取堆顶元素并删除while (!HeapEmpty(hp)){printf(%d ,HeapTop(hp));HeapPop(hp);}printf(\n);return 0;
}
大堆的实现
大堆的实现只需要将向上调整算法和向下调整算法中只需要将注释掉的语句重新启用即可
思考堆的意义是什么
1、堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤建堆与利用堆删除思想进行排序
建堆升序建大堆、降序建小堆很重要下一篇我们会对升序建大堆的办法进行详细介绍利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序重要 当一棵树为满二叉树时高度h与结点总数N的关系是h log (N 1) 当一棵树为完全二叉树时高度h与结点总数N最坏的关系是h log N 1 所以如果有一百万个数据组成一棵二叉树那么这棵树的高度仅为20十亿个数据高度仅仅为30即如果我们要用堆排序去查找100w个数据中的其中一个大概只需要查找二十次...... 补充在使用堆排序时并不能说它能更高效地维护数据的有序性。相反建立和调整一个完整的二叉树结构以及频繁进行元素交换和下沉操作可能会带来一些额外开销并且在某些情况下可能比其他简单算法慢。但是由于其稳定而可预测性能表现在某些特殊情况下仍然被认为是有效和实用的算法之一。
2、top k问题
问题描述获取N个数里找最大的前K个数N远大于K 解决思路一 N个数插入进大堆中Pop K次 时间复杂度N*logN K*logN O(N*logN) 但如果N为100亿100亿个整数需要40GB左右的内存空间而只要查找前10个数K为10 解决思路二 1、取前K个值建立K个数的小堆 2、再读取后面的值跟堆顶元素比较若大于堆顶元素交换二者位置然后重新堆化成小堆 时间复杂度O(N*logK) 注意事项必须要建立小堆不能建立大堆如果建立大堆一旦第一大的数字在建堆时位于堆顶后续第n大的数字就无法进堆同时第二大的数字可能还会被挤出去如果不信可以用[4,6,1,2,8,9,5,3]这个我随机想出来数组用以上方法取前三个最大的数字试一试 有时候你可能会很想刨根问底的知道这些办法都是怎么想出来的其实我也不知道这就跟你骑自行车的时候去思考这些链子为什么要这样组合在一起为什么组合在一起就可以产生这样的效果其实我们根本不需要思考那么多我们只需要骑上自行车去干我们要干的事情即可它只是一个用于解决我们问题的工具我们说的解题思路也是一样的这些东西都是哪些很nb的人发明出来的如果你是一个很nb的人你也不会看到这里不是前人栽树后人乘凉作为一个还没有完全深入学习数据结构的菜鸟既然已经知道了有这种解决办法那么你就直接用等你什么时候感觉自己已经很nb了再来思考为什么吧......当然也不是说都不要思考一些必要的思考还是需要的别钻牛角尖了 模拟实现 使用数组[7, 8, 15, 4, 20, 23, 2, 50]演示如何使用最小堆找出前3个最大的元素。 首先我们创建一个最小堆并将数组的前3个元素[7, 8, 15]插入堆中初始堆的表示如下 7/ \8 15 接下来遍历数组发现 4 7因此我们不做任何操作 继续遍历数组发现 20 7因此将 7 替换为 20 并重新堆化成小堆 8/ \20 15继续遍历数组发现 23 大于 8因此我们将 8 替换为 23 并重新堆化成小堆 15/ \20 23继续遍历数组发现 2 15因此我们不做任何操作 继续遍历数组发现 50 15因此我们将 15 替换为 50 并重新堆化成小堆 20/ \50 23最后数组遍历完成得到了最终的最小堆 20/ \50 23此时堆中的前3个最大元素为 [20, 50, 23]它们就是原数组中的前3个最大元素 ~over~
