网站广告设计怎么做,长春网站优化实战,网站方案书免费,金色网站模板制作不易#xff0c;三连支持一下呗#xff01;#xff01;#xff01; 文章目录 前言一、堆的概念及结构二、堆的实现三.堆的应用 总结 前言
CSDN
这篇博客介绍了二叉树中的基本概念和存储结构#xff0c;接下来我们将运用这些结构来实现二叉树 一、堆的概念及结构
1… 制作不易三连支持一下呗 文章目录 前言一、堆的概念及结构二、堆的实现三.堆的应用 总结 前言
CSDN
这篇博客介绍了二叉树中的基本概念和存储结构接下来我们将运用这些结构来实现二叉树 一、堆的概念及结构
1.概念
堆是一种完全二叉树但是堆中每个节点都不大于或不小于其父节点这样的完全二叉树就称为堆。
堆的性质堆中每个节点都值都不大于不小于其父节点的值 堆是一种完全二叉树
堆分为大堆和小堆根节点为最大值的是大堆根节点为最小值的是小堆。 2.结构
堆通常采用的是顺序存储的方式即将数据存储在数组中通过父节点和孩子节点下标的关系来相连起来。
typedef int HPDateType;typedef struct Heap
{HPDateType* a;int size;int capacity;
}HP; 二.堆的实现
1.堆的初始化和销毁
这个部分比较简单直接放代码
//初始化
void HPInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}//销毁
void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
} 2.堆的插入数据向上调整算法
每次插入数据后我们都需要调整数据的位置以保证满足堆的定义这里我们写了一个向上调整函数
//向上调整算法
void AdjustUp(HPDateType* 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;}}
}
这里我们建的是小堆所以判断条件是孩子的值小于父亲的值时就交换。
所以 push数据时在插入到size位置的基础上只需要加一个向上调整函数的调用即可。
void HPPush(HP* php, HPDateType x)
{assert(php);if (php-size php-capacity){int newcapacitty php-capacity 0 ? 4 : 2 * php-capacity;HPDateType* tmp (HPDateType*)realloc(php-a, sizeof(HPDateType)*newcapacitty);if (tmp NULL){perror(realloc:);return;}php-capacity newcapacitty;php-a tmp;}php-a[php-size] x;php-size;//向上调整AdjustUp(php-a,php-size-1);
}
下面我们分析一下向上调整算法建堆的时间复杂度 //建堆int i 0;for(i 0; i 10; i){HPPush(hp, a[i]);}
假设我们要N个节点 树的深度是h。
这样我们就可以得到 N
反解得h近似可得h约等于logN。
因为向上调整最坏情况下会调整高度次而高度约等于logN所以向上调整算法的时间复杂度就是logN。
void HPInitArray(HP* php, HPDateType* a, int n)
{assert(php);php-a (HPDateType*)malloc(sizeof(HPDateType)*n);if (php-a NULL){perror(Init:);return;}memcpy(php-a, a, n * sizeof(HPDateType));php-capacity php-size n;//建堆for (int i1; i php-size; i){AdjustUp(php-a, i);}
}
那么用向上调整算法建堆时在插入第k层的数据时最多向上调整k-1次第k层有个节点这些节点共需向上调整k-1*次。
所以时间复杂度oN1*…h-1*h-22
又因为h约等于logN
oNN*N-22。近似为N*logN 3. 删除数据向下调整算法
注意堆删除数据时是删除堆顶的数据而不是最后一个位置的数据
可能大家首先想到的删除方法是挪动数据向前一个覆盖。
但是这种方法有两个缺陷
1.这种操作的时间复杂度是oN效率不是很高。
2.这种操作完全破坏了之前建立的堆的结构最后我们还要耗费大量的操作时间来重新建堆。 因此这里我们采用另一种思路
先交换最后一个位置和堆顶元素再size--。这样我们就删除了堆顶数据并且并没有完全破坏掉堆的结构因为除堆顶数据外堆顶元素的左子树和右子树依旧还是堆结构我们只需要将堆顶元素向下调整将它放置在合理位置就可以了。
向下调整算法
//向下调整算法
void AdjustDown(HPDateType* a, int n, int parent)
{int child parent * 2 1;while(child n){if (child1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child child * 2 1;}else {break;}}
} 注意我们依旧以小堆为例在调整时我们的思路是和孩子中小的那个值比较如果孩子比父亲的值要小就交换并更新孩子和父亲的值循环操作直到终端结点。
向下调整算法的适用条件下面的节点是堆。
那么我们pop操作就比较简单了。
pop函数
//删除堆顶数据
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);
}
我们接着分析一下使用向下调整算法建堆的时间复杂度
为满足向下调整算法的条件我们从最后一个节点的父节点开始向下调整。
void HPInitArray(HP* php, HPDateType* a, int n)
{assert(php);php-a (HPDateType*)malloc(sizeof(HPDateType)*n);if (php-a NULL){perror(Init:);return;}memcpy(php-a, a, n * sizeof(HPDateType));php-capacity php-size n;//向下调整建堆for (int i (php-size - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, php-size, i);}
}
同向上调整算法类似时间复杂度O(N)1* …(h-1)*-1-h.
由满二叉树hlogN1得ONN-logN1
所以使用向下调整算法建堆的时间复杂度为ONN。
比使用向上调整建堆效率提高了非常多 4.其他一些小函数
//取堆顶数据
HPDateType HeapTop(HP* php)
{assert(php);return php-a[0];
}
//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
} 这两个函数非常简单有之前顺序表链表栈和队列的基础应该是不难理解的。 三.堆的应用 堆排序和TopK问题
1.TopK问题
TopK问题即求数据结合中前K个最大的元素或最小的元素一般情况下数据量都比较大。
比如我们要从100亿个数据中找到最大的前十个数是多少。
我们没有了解堆之前可能想法就是将数据存到一个数组中用排序算法排序一下最后取最大的十个数。
但是这样的方法实践中是不可行而且就算可行效率也不高的。
但是根据堆的性质堆顶的元素就是最大值或最小值。那如果我们要找最大的十个数我们就建小堆初始先将所以数据中的前十个元素建成一个小堆依次遍历数据如果数据比堆顶元素大就将堆顶元素替换成这个数据并向下调整保持小堆的状态。直至结束最后在小堆中的十个值就是最大的十个数。
时间复杂度ONKN-K*logK。
这里我们采用循环产生随机数的方法来创造大量随机数据来模拟TopK问题。 这样我们就创造了有10000个数据的文件并且这些数据的大小都在1000000以内。
这时我们手动在10个数据后面补位使它们大小超过1000000那么如果程序正确我们最后打印出来的值是10个比1000000大的值。 结果和预期相同证明我们都程序大概率是没什么问题的。 2.堆排序
如果我们想要将一组数排成升序我们就建大堆要排成降序就排成小堆
void HeapSort(int* a, int n)
{//建堆for (int i (n - 1 - n) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
堆排序的时间复杂度计算时和向上调整建堆一样都是N*logN我们忽略最开始建堆ON的消耗。 总结
这篇博客详细介绍了堆结构的实现和实践中的应用希望对大家有所收获。
