商洛网站建设电话,做球迷网站,什么网站流量多,骨干校建设验收网站本章的知识需要有树等相关的概念#xff0c;如果你还不了解请先看这篇文章:初识二叉树 堆的详解一、二叉树的顺序结构及实现1、二叉树的顺序结构2、堆的概念及结构二、堆的简单实现 (以大堆为例)1、堆的定义2、堆的初始化3、堆的销毁4、堆的打印5、堆的插入6、堆顶元素的获取7… 本章的知识需要有树等相关的概念如果你还不了解请先看这篇文章:初识二叉树 堆的详解一、二叉树的顺序结构及实现1、二叉树的顺序结构2、堆的概念及结构二、堆的简单实现 (以大堆为例)1、堆的定义2、堆的初始化3、堆的销毁4、堆的打印5、堆的插入6、堆顶元素的获取7、堆的删除8、堆元素个数的获取8、堆的判空10、堆简单的应用三、堆的创建1、向上调整建堆2、向下调整建堆四、堆的应用1、堆排序2、TOP-K问题一、二叉树的顺序结构及实现
1、二叉树的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 2、堆的概念及结构
严格定义如果有一个关键码的集合KKK{ k0k1k2..kn−1k_0k_1 k_2..k_{n-1}k0k1k2..kn−1 }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足: KiK2i1K_i K_{2i1}KiK2i1且Ki;K2∗i2(KiK2i1且KiK2∗i2)i01⋅⒉...K_i; K_{2*i2}(K_i K_{2i1}且K_i K_{2*i2}) i01·⒉...Ki;K2∗i2(KiK2i1且KiK2∗i2)i01⋅⒉...则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
非严格定义堆有两种分为大堆与小堆它们都是完全二叉树 大堆树中所有父亲都大于等于孩子 小堆树中所有父亲都小于等于孩子 在前一篇文章中我们也讲过,左孩子都是奇数右孩子都是偶数并且孩子和父亲下标也是有一定关系的我们也可以通过找规律得到下面的关系:
leftchild parent*21
rightchild parent*22
parent (child-1)/2 //偶数会被取整数因此可以直接按照左孩子公式反推二、堆的简单实现 (以大堆为例)
1、堆的定义
由于堆比较适合用数组存储我们可以按照顺序表的结构来进行定义但是切记数组存储是物理结构我们要把这个物理结构给抽象为完全二叉树。
//堆的结构定义
typedef int HPDateType;
typedef struct Heap
{HPDateType* a; //指向要存储的数据int size; //记录当前结构存储了多少数据int capacity; //记录当前结构的最大容量是多少
}HP;2、堆的初始化
堆的初始化我们可以给指针a开辟空间,也可以不开辟空间这里选择不开辟空间。
//堆的初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}3、堆的销毁
堆的销毁我们可以直接将空间进行释放然后将指针置空size与capacity置成0就行了。
//堆的销毁
void HeapDestroy(HP*php)
{assert(php);free(php-a); //指针置空php-a 0; //size置成0php-size php-capacity 0; //capacity置成0
}4、堆的打印
由于我们是使用数组实现堆我们可以直接遍历一遍数组将它们打印出来就行了。
//堆的打印
void HeapPrint(HP* php)
{assert(php);int i 0;for (i 0; i php-size; i){printf(%d , php-a[i]);}
}5、堆的插入
堆的插入就有一些复杂了我们的插入数据以后要保证插入数据后的堆还是一个大堆不然就破坏了堆的结构。
我们先来考虑第一种情况
我们再来考虑第二种情况 我们总结一下这两种情况 ①首先在我们插入数据子节点之前原始堆就要满足堆的结构否则就是前面的代码出现了问题与我们插入的数据无关
②然后插入的子节点要与其父节点进行比较如果小于其父节点则不交换正常插入。如果其插入的子节点大于父节点就要进行向上调整交换这个交换次数是不确定的可能是一次也可能是两次不过最多就是树的高度hlog2Nh\log_2Nhlog2N次(NNN为节点个数),这也就是说我们的堆的插入是时间复杂度是O(log2n)O(\log_2n)O(log2n)
接下来就是我们要根据这两种情况写出相应的代码了这个时候这个孩子和父亲下标关系就很重要了,通过这个关系我们就能由子节点找到父节点由父节点找到子节点了。
//堆的插入
void HeapPush(HP* php, HPDateType data)
{assert(php);//判断是否需要扩容if (php-capacity php-size){int new_capacity php-capacity 0 ? 4 : php-capacity * 2;HPDateType* tmp (HPDateType*)realloc(php-a, sizeof(HPDateType)*new_capacity);//realloc对于没有进行动态内存分配过的指针 调用会相当与一次mallocif (NULL tmp){perror(malloc fail:);exit(-1);}php-a tmp;php-capacity new_capacity;}//数据插入php-a[php-size] data;php-size;//向上调整AdjustUp(php-a,php-size-1);
}其中向上调整算法非常重要
//交换函数
void Swap(HPDateType* x, HPDateType* y)
{HPDateType tmp *x;*x *y;*y tmp;
}
//向上调整
void AdjustUp(HPDateType*a,int child)
{assert(a);int parent (child - 1) / 2; //找到刚插入的节点的父节点while (child0) //child0说明子节点已经调整到了堆顶已经不需要再进行调整了。{if (a[child] a[parent]) //子节点比父节点大就交换{Swap(a[child], a[parent]);child parent; //更改孩子的下标方便继续与上面新的父节点比较parent (child - 1) / 2; //更改父节点的下标方便继续与下面新的子节点比较}else{break;//比较不满足条件说明数据经过调整后已经符合大堆了}}
}6、堆顶元素的获取
对于堆来说堆顶的数据一定是堆里面最大或最小的数所以堆顶数据的获取还是很有必要的它的实现也并不复杂。
//堆顶元素的获取
HPDateType HeapTop(HP*php)
{assert(php);assert(php-size 0);return php-a[0];
}7、堆的删除
对于堆的删除一般是删除堆顶元素因为除了堆顶元素其他元素删除的意义并不大但是堆顶的元素删除又会破环堆的结构。 而且如果采用直接删除堆顶元素其他元素向前挪动之后再进行调整的话会有很大的浪费因为数组向前挪动的时间复杂度是O(n)O(n)O(n)。但是数组的尾删效率很高是O(1)O(1)O(1),所以数组尽量进行尾删。
于是便有了一种良好的先交换再向下调整的算法它的思想是先让堆顶元素与最后一个元素交换位置这样原先的堆顶元素就变成了堆底元素然后删除堆底元素再对堆顶的元素进行向下调整其核心算法就在于向下调整。 向下调整算法 向下调整算法要求我们先取堆顶元素的子节点中较大的那个与堆顶元素进行比较如果子节点大于父节点就进行交换然后父节点的下标变到原先子节点的下标再次执行上面的步骤取父节点下面较大的子节点进行比较换位… 直到子节点不大于父节点或者是超出了数组边界。
//堆的删除
void HeapPop(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 AdjustDown(HPDateType* a, int n, int parent)
{//假设左孩子是最大的int child parent * 2 1;while (childn){//判断假设是否正确若不正确进行更改if (a[child 1] a[child]){child;}if (child 1 n a[child] a[parent]){Swap(a[child],a[parent]);parent child;child parent * 2 1;}else{break;}}
}向下调整的算法与向上调整类似这个交换次数是不确定的可能是一次也可能是两次不过最多就是树的高度hlog2Nh\log_2Nhlog2N次(NNN为节点个数),这也就是说我们的堆的删除是时间复杂度也是O(log2n)O(\log_2n)O(log2n) 比较一下向上调整算法与向下调整算法 向上调整算法要求数据插入之前原先的数据已经是一个堆了才能重新建堆。向下调整算法的要求左右子树必须是一个堆才能调整重新建堆。 8、堆元素个数的获取
堆中的元素个数其实就是堆数据结构中的size。
// 堆元素个数的获取
int HeapSize(HP* php)
{assert(php);return php-size;
}8、堆的判空
//堆的判空
bool HeapEmpty(HP* php)
{assert(php);return (php-size 0);
}10、堆简单的应用
学习到了这里我们其实已经能利用堆处理一些问题了。
TOP-K问题 堆顶的元素是最大小的元素我们可以取堆顶K次删除K次拿到一个数据集中最大小的前K个。
int main()
{HP hp;HeapInit(hp); //堆的初始化int arr[] { 27,15,19,18,28,34,65,49,25,37 };for (int i 0; i sizeof(arr) / sizeof(int); i) //堆的插入建堆{HeapPush(hp, arr[i]);}HeapPrint(hp); //打印堆中的元素printf(\n);//选出最大的前五个int k 5;for (int i 0; i k; i){printf(%d , HeapTop(hp)); //取堆顶的元素HeapPop(hp); //删除堆顶元素重新定位新的最大的。}HeapDestroy(hp); //堆的销毁防止内存泄漏return 0;
} 排序问题 排序问题与TOP-K问题类似只不过这里的K是所有元素。
int main()
{HP hp;HeapInit(hp);int arr[] { 27,15,19,18,28,34,65,49,25,37 };for (int i 0; i sizeof(arr) / sizeof(int); i){HeapPush(hp, arr[i]);}HeapPrint(hp);printf(\n);//排序while(!HeapEmpty(hp))//只要不为空就一直进行排序。{printf(%d , HeapTop(hp));HeapPop(hp);}HeapDestroy(hp);return 0;
} 三、堆的创建
在上面的代码中我们看到我们经常会用一个数组去创建堆因此我们还是很有必要再写一个函数——堆的创建在上面的代码中我们创建一个堆其实是用的是堆的插入即将数据插入到数组最后再进行向上调整。这种方法能帮我们完成堆的创建但是它的效率并不是很高我们可以对其做一定优化。
1、向上调整建堆
利用堆的插入进行堆的创建
void HeapCreat(HP* php, HPDateType* arr, int n)
{assert(php);HPDateType* tmp (HPDateType*)malloc(sizeof(HPDateType) * n);if (NULL tmp){perror(malloc fail:);exit(-1);}php-a tmp;php-capacity n;for (int i 0; i n; i){HeapPush(php, arr[i]);//这里使用了AdjustUp()函数}
}但是这种建堆算法效率比较低我们来求一下它的时间复杂度。 按照最坏的情况来算完全二叉树的最坏情况是满二叉树且每个节点都要调整 向上调整建堆的第一层是不进行调整的设FFF是建堆交换调整的总次数h−1h-1h−1是树的高度NNN是树的结点个数,则有 F21∗122∗223∗3......2h−2∗h−22h−1∗h−1F2^1*12^2*22^3*3......2^{h-2}*h-22^{h-1}*h-1 F21∗122∗223∗3......2h−2∗h−22h−1∗h−1 利用错位相减法得 F(h−2)∗2h1(1)F(h-2)*2^h1 \tag{1} F(h−2)∗2h1(1) 又因为二叉树满足 N20212223......2h−22h−12h−1(2)N2^02^12^22^3......2^{h-2}2^{h-1}2^h-1\tag{2} N20212223......2h−22h−12h−1(2) 将2带入1中得 F(N1)∗(log2(N1)−2)1(3)F(N1)*(\log_2{(N1)}-2)1\tag{3} F(N1)∗(log2(N1)−2)1(3) 因此向上调整建堆的时间复杂度是O(nlog2n)O(n\log_2n)O(nlog2n)
2、向下调整建堆
向下调整算法是有的要求的左右子树必须是一个堆才能调整重新建堆但给我们的数组本身就是乱序的那我们应该怎样才能保证左右子树是一个堆呢 答案是我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。
在这里第一个非叶子节点的子树是28,我们可以通过子节点与父节点的关系找到28的下标然后向下调整让①区域变成堆然后下标减一到18的位置然后向下调整让②区域变成堆然后下标减一到19的位置然后向下调整让③区域变成堆…直到下标为零时再调整一次这样就把堆给建立起来了。 代码实现
//堆的创建
void HeapCreat(HP* php, HPDateType* arr, int n)
{assert(php);HPDateType* tmp (HPDateType*)malloc(sizeof(HPDateType) * n);if (NULL tmp){perror(malloc fail:);exit(-1);}php-a tmp;php-sizephp-capacity n;memcpy(php-a, arr, sizeof(HPDateType)*n);//内存拷贝函数for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, n, i); //利用向下调整算法}}这种建堆算法效率是比较高的我们来求一下它的时间复杂度。 按照最坏的情况来算完全二叉树的最坏情况是满二叉树且每个节点都要调整 由于向下调整建堆是从倒数第二层开始调整的所以我们假设树的高度为hhh,FFF是建堆交换调整的总次数NNN是树的结点个数。 F2h−2∗12h−3∗22h−4∗3......21∗h−220∗h−1(1)F2^{h-2}*12^{h-3}*22^{h-4}*3......2^1*h-22^0*h-1\tag{1} F2h−2∗12h−3∗22h−4∗3......21∗h−220∗h−1(1) 利用错位相减法得 F2h−(h1)(2)F2^h-(h1) \tag{2} F2h−(h1)(2) 又因为二叉树满足 N20212223......2h−22h−12h−1(2)N2^02^12^22^3......2^{h-2}2^{h-1}2^{h}-1\tag{2} N20212223......2h−22h−12h−1(2) 将2带入1中得 FN−(log2(N1)1)(3)FN-(\log_2{(N1)}1)\tag{3} FN−(log2(N1)1)(3) 因此向下调整建堆的时间复杂度是O(n)O(n)O(n)
综上所述向下调整建堆是更好的算法。 对比我们也可以发现向上调整算法是那一层节点越多向上调整越多而向下调整算法是那一层节点越少向下调整越多。因此向下调整算法更加优秀
四、堆的应用
在前面我们已经简单说过了堆的应用TOP-K与排序。
1、堆排序
但是上面的应用我们都是借助了堆这个数据结构利用了堆的插入与删除在实际应用时给你一个数组让你进行排序难道我们还要费很大的力气去建堆这样显然太慢了所以我们需要找到一种不用建立堆的数据结构就能进行排序的算法。
首先经过前面的学习我们都知道了每个连续存储的数组可以看成一个完全二叉树因此我们可以利用刚才堆的创建的思路对数组里面的数据进行建堆然后进行排序。
但是假设我们要建立升序数组我们应该建立大堆还是小堆呢
我们先来看看小堆怎么样。
假设我们建立小堆的话第一个元素就不用进行排序了我们从第二个进行排序但是从第二个元素开始重新排序的话我们的堆结构可能就被破坏了不利于我们后续选数据要不就是遍历一遍选一个数这些效率都不太好。因此小堆并不适合建立升序数组。
我们再来看看大堆 我们可以将堆顶元素与堆底元素进行换位这样我们最大的元素就到了正确的位置然后对堆顶元素向下调整一次便可以重新建堆因为左子树与右子树关系没有改变再然后把最后一个元素不看成堆里面的元素再将堆顶元素与堆底元素进行换位这样我们次大的元素就到了正确的位置然后对堆顶元素向下调整一次便可以重新建堆再然后把最后两个元素不看成堆里面的元素如此继续循环往复等数组里面的数被遍历一遍后排序也就结束了另外我们向下调整一次最多交换高度次log2n\log_2nlog2n,因此堆排序的时间复杂度是O(nlog2n)O(n\log_2n)O(nlog2n)。 //堆排序 升序建立大堆降序建小堆
void HeapSort(HPDateType* arr, int n)
{int parent (n - 1 - 1) / 2;//建堆 --Onwhile(parent0){AdjustDown(arr, n, parent);--parent;}//排序 --O(nlogn)int end n - 1;while (end0){Swap(arr[0], arr[end]);//向下调整重新建堆AdjustDown(arr, end, 0);--end;}
}
int main()
{int arr[] { 27,15,19,18,28,34,65,49,25,37 };int n sizeof(arr) / sizeof(int);HeapSort(arr, n);for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);
}2、TOP-K问题
在前面堆的简单应用中我们也简单的学习了用堆的数据结构进行解决TOP-K问题我们建立一个大堆对堆顶元素进行删除拿到第一个数据再重新向下调整建堆再对堆顶元素进行删除拿到第二个数据…如此往复便解决了TOP-K的问题。
但是一般情况下TOP-K问题的数据量都比较大我们再利用上面的方法可能就不太行了例如从100亿个数据中选择10个最大的假设全是整数那么需要400亿字节而1G≈10亿字节我们用数组存储这100亿个数就需要40G的内存这显然内存不足于是我们就需要把这么多的数据放进硬盘中了利用文件读取来读取数据可是硬盘中的数据并不能建堆于是我们就要考虑其他的算法了。
我们可以建立一个KK为要想要选取的数的个数个数据的小堆从文件中读取数据与堆顶的元素进行比较如果大于堆顶元素就替换掉堆顶元素然后向下调整重新建立小堆这样经过遍历所有数后想要的K个数就在小堆里面
代码示例
int main()
{//选最大的5个数int randK 5;//打开文件FILE* pfin fopen(data.txt, w);if (NULL pfin){perror(fopen fail:);return;}//设置随机种子srand(time(NULL));int val 0;for (int i 0; i 500; i){//插入5个明显更大的数据方便判断TOP-K结果是否正确if (i ! 0 i % 7 0 randK 0){fprintf(pfin, %d , 1000 i);randK--;continue;}//造500个随机数val rand() % 1000;fprintf(pfin, %d , val);}//关闭文件fclose(pfin);//以读的方式打开文件FILE* pfout fopen(data.txt, r);if (NULL pfout){perror(fopen fail:);return;}//取5个数建立小堆int min_heap[5];for (int i 0; i 5; i){fscanf(pfout, %d, min_heap[i]);}for (int i (5 - 1 - 1) / 2; i 0; --i){AdjustDown(min_heap, 5, i);}while (fscanf(pfout, %d, val) ! EOF){if (val min_heap[0]){min_heap[0] val;AdjustDown(min_heap, 5, 0);}}fclose(pfout);//打印堆中的数据for (int i 0; i 5; i){printf(%d , min_heap[i]);}return 0;
}
