阿里云esc建设网站,近三天时政热点,物流网站建设 市场分析,新做好的网站如何做seo文章目录 前言堆一、什么是堆二、堆又分为大根堆和小根堆三、由于堆的逻辑结构被看成完全二叉树#xff0c;那么我们先来了解一下完全二叉树。四、堆使用数组还是链表储存数据呢#xff1f;五、数组构建二叉树和父子节点之间的定位六、堆进行的操作七、实现小根堆1、堆的初始… 文章目录 前言堆一、什么是堆二、堆又分为大根堆和小根堆三、由于堆的逻辑结构被看成完全二叉树那么我们先来了解一下完全二叉树。四、堆使用数组还是链表储存数据呢五、数组构建二叉树和父子节点之间的定位六、堆进行的操作七、实现小根堆1、堆的初始化2、堆在数组尾部插入3、堆在数组头部删除4、获取堆顶的元素5、获取堆的元素个数6、判断堆是否为空7、堆的销毁8、总代码一览 堆的应用一、堆排序1、原理2、代码实现 二、TOP-K问题 堆练习一、数组中两个元素的最大乘积一、最小数字游戏 前言
1、本文章适合新学和复习用都是用c语言实现的包含了堆的讲解、堆的应用、堆的练习。 2、有图解和代码都注释放心食用哦
那么开始
堆
一、什么是堆 堆(Heap)是计算机科学中一类特殊的数据结构是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组。 二、堆又分为大根堆和小根堆 大根堆父节点大于左右孩子节点 。 小根堆父节点小于左右孩子节点。 大小根堆图
三、由于堆的逻辑结构被看成完全二叉树那么我们先来了解一下完全二叉树。 完全二叉树:完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。 完全二叉树与非完全二叉树图
四、堆使用数组还是链表储存数据呢
我建议使用数组 数组的优点 1方便定位可以通过子节点求父节点也可以通过父节点求子节点。 2占用空间相对链表小。 3堆的逻辑结构是完全二叉树完全二叉树使用数组可以实现连续存储不会浪费多余的空间 数组的缺点 要经常扩容效率降低。 利大于弊所以数组是一个很好的选择。
五、数组构建二叉树和父子节点之间的定位 六、堆进行的操作 a.在尾部插入元素。 b.在头部删除元素 。 c.在头部获取元素。 d.察看堆的元素个数。 f.判断堆是否为空。 这些操作是不是很熟悉捏其实这些操作和队列是一样的但是abd这些核心操作和普通队列是完全不一样的因为插入和删除利用了堆来实现使最大元素大根堆或者最小元素小根堆放到顶部取元素的时候取的是最大或者最小的元素这使队列不在是先进先出而是大元素或者小的元素先出又因为堆的效率很高所以我们也将其称为最高效的优先队列。 堆与普通队列对比
七、实现小根堆
1、堆的初始化
开始对堆的结构体的成员进行初始化如数组容量数组大小申请空间。
堆的结构体
//定义数据类型
typedef int DATATYPE ;
//堆结构体
typedef struct priority_queues
{//数组DATATYPE* arr;//大小 指向的是有数据后的一个位置int size;//容量int capacity;
}pq;对堆结构体的初始化
//初始化
void IintQueue(pq* p)
{//断言判断assert(p);p-arr NULL;//开始下标为0p-size 0;//开始我们给一个容量为4p-capacity 4;//申请一个空间大小为4DATATYPE* tmp (DATATYPE*)realloc(p-arr, sizeof(DATATYPE) * p-capacity);//判断是否申请成功if (tmp NULL){printf(申请失败);exit(-1);}p-arr tmp;
}2、堆在数组尾部插入 (1)堆在插入元素是一个核心的操作就是要进行调整进行建小根堆使最小的元素调整到堆顶的位置。 (2)那么如何建小根堆呢 我们接下来学习一个方法向上调整法 那么向上调整法是从哪里开始调整呢答案是每一个新插入的元素。 第一步利用孩子的下标插入数据的下标child 找到父节点的下标father:father (child-1) / 2。 第二步保存孩子的元素tmp 。 第三步用孩子节点的元素和父节点元素对比若孩子的元素比父亲的大就直接打破调整结束若孩子节点的元素比父亲节点的元素小就将父节点的元素节点赋给孩子节点并child father 让之前父节点的位置作为新孩子下标继续寻找下一个父节点的下标father (child-1) / 2, 以此往上调整直到遇到比tmp大的父节点或者child 0没有父节点时调整结束。 (3)图解
(4)代码实现
//向上调整
void AdjustUpwards(DATATYPE* arr, int child)
{//父节点下标int father 0;father (child - 1) / 2;//保存插入元素DATATYPE tmp arr[child];while (child 0){if (arr[father] tmp){break;}else{arr[child] arr[father];child father; //改变子节点下标father (child - 1) / 2;//再找父节点下标}}//返回元素arr[child] tmp;
}(5)接下来就是插入元素将元素插入到尾部并进行调整。 代码实现
//插入元素
void Priority_Queue_Push(pq* p, DATATYPE val)
{//断言assert(p);//判断是否满了if (p-size p-capacity){DATATYPE* tmp (DATATYPE*)realloc(p-arr, sizeof(DATATYPE) * p-capacity * 2);if (tmp NULL){printf(申请失败);exit(-1);}p-arr tmp;p-capacity p-capacity * 2;}//插入数据p-arr[p-size] val;p-size;//调整AdjustUpwards(p-arr, p-size-1);}经过上述步骤之后堆顶的数据就是整个堆中最小的元素了 (6)插入操作的时间复杂度 最坏的情况从底位置到0 走h层次高度, n数组大小2^h层次高度-1所以hlogn-1以2为底 最好的情况不需要调整 综上时间复杂度为 OlongN 3、堆在数组头部删除 (1)怎么样将头部元素删除呢我们是用数组最后的一个元素将第一个元素覆盖即arr[0] arr[size-1]并且size–但是这样就会破坏掉我们的堆因此我们还要学习另一个方法去重新调整堆这个方法就向下调整法。 (2)向下调整法 向下调整法顾名思义就是向下调整堆那么从哪里向下呢答案是从父节点向下。 第一步利用需要调整的下标作为父节点下标找到左右孩子节点的下标。 第二步保存该父节点下标的元素tmp。 第三步先找到左右孩子中元素大小最小的再将其与tmp对比若是tmp小于孩子节点左或右孩子元素arr[father] tmp,然后结束调整若tmp大于孩子节点元素就将孩子节点的元素赋给父节点位置再改变父节点下标使孩子节点的下标作为父节点下标再重新寻找新的孩子下标arr[father] arr[child] , father child ,child father*21 或 child father*22直到遇到比tmp大的孩子节点元素左或右孩子时或者child size-1时结束调整。 (3)图解 (4)代码实现
//向下调整
void Build_Biles(DATATYPE* arr, int father,int size)
{//找左孩子节点和保存数据int child father * 2 1;int tmp arr[father];while (child size){//找最小那个孩子节点if (child 1 size arr[child] arr[child 1]){child;}//对比if (tmp arr[child]){arr[father] arr[child];father child;child father * 2 1;}else{break;}}//返回元素arr[father] tmp;
}(5)删除操作代码实现
//弹出数据
bool Priority_Queue_Pop(pq* p)
{assert(p);//为空无法删除if (p-size 0){return false;}//只有一个元素时无需调整else if (p-size 1){p-size--;}//存在多个元素时需要调整else{p-arr[0] p-arr[p-size - 1];p-size--;//调整Build_Biles(p-arr, 0, p-size);}return true;
}经过上述步骤之后数组调整为小堆 (6)删除操作的时间复杂度 最坏的情况从0位置到底走h层次高度 n数组大小2^h层次高度-1所以hlogn-1以2为底 最好的情况不需要调整 综上时间复杂度为 OlongN 4、获取堆顶的元素
通过判断堆如果不为空就可以返回堆顶元素要是为空就返回-1堆顶元素就是下标为 0 的位置并且该元素是整个堆最小的元素。
代码实现
//返回数据
DATATYPE Priority_Queue_Top(pq* p)
{assert(p);//判断是否为空if (p-size 0){return -1;}return p-arr[0];
}5、获取堆的元素个数
直接返回结构体中的size即可。
代码实现
//返回元素个数
int Priority_Queue_Size(pq* p)
{assert(p);return p-size;
}6、判断堆是否为空
通过判断结构体中的size是否为0即可判断是否为空了。
代码实现
//判断是否为空
bool Priority_Queue_Enpty(pq* p)
{assert(p);return p-size 0;
}7、堆的销毁
对数组进行释放初始化结构体其他成员。
//销毁
void Priority_Queue_Destroyed(pq* p)
{assert(p);//释放数组free(p-arr);p-arr NULL;//初始化成员p-capacity 0;p-size 0;
}8、总代码一览
priority_queue.h
#pragma once
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef int DATATYPE ;
//结构体
typedef struct priority_queues
{//数组DATATYPE* arr;//大小int size;//容量int capacity;
}pq;//向下调整
void Build_Biles(DATATYPE* arr, int begin, int end);//向上调整
void AdjustUpwards(DATATYPE* arr, int begin);//初始化
void IintQueue(pq *p);//插入元素
void Priority_Queue_Push(pq *p, DATATYPE val);//弹出数据
bool Priority_Queue_Pop(pq* p);//返回队头数据
DATATYPE Priority_Queue_Top(pq* p);//判断是否为空
bool Priority_Queue_Enpty(pq* p);//返回元素个数
int Priority_Queue_Size(pq* p);//销毁
void Priority_Queue_Destroyed(pq* p);priority_queue.c
#include priority_queue.h
//初始化
void IintQueue(pq* p)
{//断言判断assert(p);p-arr NULL;//开始下标为0p-size 0;//开始我们给一个容量为4p-capacity 4;//申请一个空间大小为4DATATYPE* tmp (DATATYPE*)realloc(p-arr, sizeof(DATATYPE) * p-capacity);//判断是否申请成功if (tmp NULL){printf(申请失败);exit(-1);}p-arr tmp;
}//向下调整
void Build_Biles(DATATYPE* arr, int father,int size)
{//找左孩子节点和保存数据int child father * 2 1;int tmp arr[father];while (child size){//找最小那个孩子节点if (child 1 size arr[child] arr[child 1]){child;}//对比if (tmp arr[child]){arr[father] arr[child];father child;child father * 2 1;}else{break;}}//返回元素arr[father] tmp;
}//向上调整
void AdjustUpwards(DATATYPE* arr, int child)
{int father 0;father (child - 1) / 2;DATATYPE tmp arr[child];while (child 0){if (arr[father] tmp){break;}else{arr[child] arr[father];child father;father (child - 1) / 2;}}arr[child] tmp;
}//插入元素
void Priority_Queue_Push(pq* p, DATATYPE val)
{assert(p);if (p-size p-capacity){DATATYPE* tmp (DATATYPE*)realloc(p-arr, sizeof(DATATYPE) * p-capacity * 2);if (tmp NULL){printf(申请失败);exit(-1);}p-arr tmp;p-capacity p-capacity * 2;}p-arr[p-size] val;p-size;//调整AdjustUpwards(p-arr, p-size-1);}//弹出数据
bool Priority_Queue_Pop(pq* p)
{assert(p);//为空无法删除if (p-size 0){return false;}//只有一个元素时无需调整else if (p-size 1){p-size--;}//存在多个元素时需要调整else{p-arr[0] p-arr[p-size - 1];p-size--;//调整Build_Biles(p-arr, 0, p-size);}return true;
}//返回数据
DATATYPE Priority_Queue_Top(pq* p)
{assert(p);if (p-size 0){return -1;}return p-arr[0];
}//判断是否为空
bool Priority_Queue_Enpty(pq* p)
{return p-size 0;
}//返回元素个数
int Priority_Queue_Size(pq* p)
{assert(p);return p-size;
}//销毁
void Priority_Queue_Destroyed(pq* p)
{assert(p);free(p-arr);p-arr NULL;p-capacity 0;p-size 0;
}以上就是堆的全部内容了上面实现的小根堆要是想实现大根堆的话就将向下向上调整法的大于小于号改一下即可
堆的应用
一、堆排序
实现升序要是想实现降序改一下向下调整法的大于小于号即可哦
1、原理 (1)第一步先将数组调整为大堆。 (2)用我们上面学的向下调整法来将数组调整为大堆那么从哪里开始向下调整呢从第一非叶节点没有左右孩子的位置开始到0的位置就完成建堆求第一个非叶节点公式father (size-1-1)/2size是数组大小。 (3)第三步大堆使最大元素到堆顶之后将堆顶元素和数组最后一个元素(假设下标为end)交换就可以将最大元素放到最后了然后重新建堆(除了第一次其他是从0下标开始调整即可)最后 end--再将堆顶元素和堆的倒数第二个元素交换以此类推直到end0这样就完成排序了 (4)图解
2、代码实现
//向下调整
void Build_Biles(DATATYPE* arr, int end,int size)
{//找左孩子节点和保存数据int father end;int child father * 2 1;int tmp arr[father];while (child size){//找最小那个孩子节点if (child 1 size arr[child] arr[child 1]){child;}//对比if (tmp arr[child]){arr[father] arr[child];father child;child father * 2 1;}else{break;}}//返回元素arr[father] tmp;
}
//交换
void Swap(int* a, int* b) {int t *a;*a *b;*b t;
}void HeapSort(int* arr, int size) {//建堆size-1-1就是除2求子树公式反过来用最后减一是因为我们求的是下标for (int i (size - 1 - 1) / 2; i 0; i--) {Build_Biles(arr, i, size);}int ned size - 1;//最后一个下标位置开始和下标为0的元素交换一直交换下去并且交换一次就调整一次//当ned1之后再进行一次交换就算排好了此时调整算法不会奏效了while (ned 0) {Swap(arr[0], arr[ned]);Build_Biles(arr, 0, ned);//重新调整ned--;}
}
int main()
{int arr[] { 1,5,3,2,4 };HeapSort(arr, 5);for (int i 0; i 5; i){printf(%d , arr[i]);}return 0;
}运行结果
二、TOP-K问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 假设我们要求在n10000整形元素中求前k10最大的。 按照上面的思路来 (1)前k个最大的所以我们建小堆。 (2)先用数组前k个元素去建小堆然后与后k-n个元素对比比堆顶元素大的就将堆顶元素与这个元素交换 代码实现
//上面是小根堆我就不复制过来了和上面的堆代码一样知道接口就行了void PrintTopK(int* arr, int n, int k)
{//初始化小根堆pq p;IintQueue(p);//前k个插入for (int i 0; i k; i){Priority_Queue_Push(p, arr[i]);}//k-n进行对比for (int i k; i n; i){//存在更大的就先删除堆顶在插入int tmp Priority_Queue_Top(p);if (arr[i] tmp){Priority_Queue_Pop(p);Priority_Queue_Push(p, arr[i]);}}//打印结果while (!Priority_Queue_Enpty(p)){int t Priority_Queue_Top(p);Priority_Queue_Pop(p);printf(%d \n, t);}}void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int) * n);srand(time(0));//初始话10000个数for (size_t i 0; i n; i){a[i] rand() % 1000000;}//设置10最大的数a[5] 1000000 1;a[1231] 1000000 2;a[531] 1000000 3;a[5121] 1000000 4;a[115] 1000000 5;a[2335] 1000000 6;a[9999] 1000000 7;a[76] 1000000 8;a[423] 1000000 9;a[3144] 1000000 10;PrintTopK(a, n, 10);
}
int main()
{TestTopk();return 0;
}运行结果
堆练习
一、数组中两个元素的最大乘积
1、题目链接数组中两个元素的最大乘积 2、题目描述 给你一个整数数组 nums请你选择数组的两个不同下标 i 和 j使 (nums[i]-1)*(nums[j]-1) 取得最大值。 请你计算并返回该式的最大值。 3、例子: 示例 1 输入nums [3,4,5,2] 。 输出12 。 解释如果选择下标 i1 和 j2下标从 0开始则可以获得最大值(nums[1]-1)(nums[2]-1) (4-1)(5-1) 3*4 12 。 4、思路 (1)其实这题很简单就是排序然后取最大的两个数即可但是我们尝试用堆去解决这个问题。 (2)用堆的话我们要构建大根堆可以将数组中的元素全部插入到堆中然后取堆顶的元素然后再删除再取即可拿到最大的两个元素了。 5、代码实现
//上面的是堆下面才是主要部分
int maxProduct(int* nums, int numsSize) {//初始化pq q;IintQueue(q);//将全部元素插入for(int i0;inumsSize;i){Priority_Queue_Push(q,nums[i]);}//取两个元素int tmp1Priority_Queue_Top(q);Priority_Queue_Pop(q);int tmp2Priority_Queue_Top(q);Priority_Queue_Pop(q);//释放堆Priority_Queue_Destroyed(q);return (tmp1-1)*(tmp2-1);
}一、最小数字游戏
1、题目链接最小数字游戏 2、题目描述 你有一个下标从 0 开始、长度为 偶数 的整数数组 nums 同时还有一个空数组 arr 。Alice 和 Bob决定玩一个游戏游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下 每一轮Alice 先从 nums 中移除一个 最小 元素然后 Bob 执行同样的操作。 接着Bob 会将移除的元素添加到数组 arr 中然后 Alice 也执行同样的操作。 游戏持续进行直到 nums 变为空。 返回结果数组 arr 。 3、例子 示例 1 输入nums [5,4,2,3] 输出[3,2,5,4] 解释第一轮Alice 先移除 2 然后 Bob 移除 3 。然后Bob 先将 3 添加到 arr 中接着 Alice 再将 2 添加到 arr 中。于是 arr [3,2] 。第二轮开始时nums [5,4] 。Alice 先移除 4 然后 Bob 移除 5 。接着他们都将元素添加到 arr 中arr变为 [3,2,5,4] 。 4、思路: (1)这一题也是可以通过排序然后再取对应的元素进新数组里的还是一样我们用堆做。 (2)因为是找小的元素先所以我们建小根堆再通过建全部元素插入到堆里每轮取出两个元素取第一个元素先保存再删除接着取第二个元素保存再删除然后将第二个取出的元素放进数组再将第一个取得元素放进数组一直循环这个操作直到堆为空即可。 5、代码实现 //上面是小根堆就不写了int* numberGame(int* nums, int numsSize, int* returnSize) {int *arr(int*)malloc(sizeof(int)*numsSize);//初始化对象pq q;IintQueue(q);//插入for(int i0;inumsSize;i){Priority_Queue_Push(q,nums[i]);}//i控制数组下标int i0;while(!Priority_Queue_Enpty(q)){//每轮取两个数int tmp1Priority_Queue_Top(q);Priority_Queue_Pop(q);int tmp2Priority_Queue_Top(q);Priority_Queue_Pop(q);arr[i]tmp2;arr[i]tmp1;}//释放Priority_Queue_Destroyed(q);*returnSizenumsSize;return arr;
}结束了喔
最后感谢大家的观看
