平度网站整站优化外包公司,1 建设网站目的是什么,个人网页设计教程,在菲做平台网站目录
一.堆的概念及结构
1.1.堆的概念
1.2.堆的存储结构
二.堆的功能实现
2.1.堆的定义
2.2.堆的初始化
2.3.堆的销毁
2.4.堆的打印
2.5.堆的插入
向上调整算法
堆的插入
2.6.堆的删除
向下调整算法
堆的删除
2.7.堆的取堆顶元素
2.8.堆的判空
2.9.堆的求堆的…目录
一.堆的概念及结构
1.1.堆的概念
1.2.堆的存储结构
二.堆的功能实现
2.1.堆的定义
2.2.堆的初始化
2.3.堆的销毁
2.4.堆的打印
2.5.堆的插入
向上调整算法
堆的插入
2.6.堆的删除
向下调整算法
堆的删除
2.7.堆的取堆顶元素
2.8.堆的判空
2.9.堆的求堆的大小
三.堆的创建
3.1.向上调整建堆
时间复杂度
3.2.向下调整建堆
时间复杂度
四.堆的应用
4.1.堆排序
步骤一建堆
步骤二排序
4.2.TOP-K问题 一.堆的概念及结构
1.1.堆的概念
若n个关键字序列L[1...n]满足下面某一条性质则称为堆(Heap)
若满足L(i)L(2i)且L(i)L(2i1)(1in/2)--大根堆(大顶堆)若满足L(i)L(2i)且L(i)L(2i1)(1in/2)--小根堆(小顶堆)
大根堆在逻辑视角上可以看成所有子树根左右的完全二叉树。相应的小根堆也可以看成根左右的完全二叉树。 堆的性质
堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。
1.2.堆的存储结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。 二.堆的功能实现
2.1.堆的定义
typedef int HPDataType;typedef struct Heap
{HPDataType* a;//开辟一个动态数组aint size;//当前元素个数int capacity;//数组的最大容量
}HP;
定义一个struct来保存堆的信息主要包含数组首元素的地址a数组中当前元素个数size以及数组的最大容量capacity。堆的定义同顺序表的定义类似。
2.2.堆的初始化
void HeapInit(HP* php)
{//判空assert(php);//将数组首元素的地址位置空php-a NULL;php-size php-capacity 0;
}
在初始化堆之前首先需要对传入的参数php进行断言判断其是否为空然后将数组首元素的地址置为空NULL最后再将size和capacity都初始化为0。
调试分析 2.3.堆的销毁
void HeapDestory(HP* php)
{//判空assert(php);//释放free(php-a);php-a NULL;php-size php-capacity 0;
}
在销毁堆之前首先需要对传入的参数php进行断言判断其是否为空然后调用free函数释放数组首元素的地址并将数组首元素的地址置为空NULL最后再将size和capacity都置为0。
调试分析 2.4.堆的打印
void HeapPrint(HP* php)
{//判空assert(php);//打印for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}
首先判断传入的参数php是否为空然后进行for循环依次打印数组中的各个元素。
2.5.堆的插入
当在堆中插入新元素时对于小根堆新元素放到表尾与父结点对比若新元素比父结点更小则将二者互换。新元素就这样一路向上调整直到无法继续上升为止。
向上调整算法
当在堆的末尾插入一个新元素而新插入的元素可能会破坏堆的性质这时就要进行调整。以小堆为例当新元素大于其对应的父结点则满足堆的性质无需调整当新元素小于其对应的父结点则不满足堆的性质要进行调整。 调整规则
若新插入的元素child小于其对应的父结点parent则调用Swap函数将二者进行交换此时child来到父结点parent的位置其对应的新的父结点的下标为(child-1)/2然后将child继续与parent进行比较依次往上执行直到child大于其对应的父结点parent则跳出循环。
循环判断条件为child0这是考虑到最坏的情况也就是当child一直小于其对应的父结点时child经过最后一次交换来到根结点的位置时此时堆的调整已经结束。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向上调整(小堆)
void AdjustUp(HPDataType* a, int child)
{//查找父结点下标int parent (child - 1) / 2;//最坏情况是一路调整到根while (child 0){if (a[child] a[parent])//大堆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, sizeof(HPDataType) * newCapacity);//判空if (tmp NULL){printf(realloc fail\n);exit(-1);}//将新开辟的内存空间的首地址tmp赋值给aphp-a tmp;//更新capacityphp-capacity newCapacity;}//插入//先将元素插入到堆的末尾即最后一个孩子后面//插入之后如果堆的性质遭到了破坏则将新插入结点顺着其双亲往上调整到合适的位置php-a[php-size] x;//注意size指向数组最后一个元素的下一个位置php-size;//向上调整AdjustUp(php-a, php-size - 1);
}
在堆中插入元素之前首先需要检查当前容量是否为空或者已满。若容量为空则调用realloc函数开辟四个元素的内存空间若容量已满则调用realloc函数将内存空间开辟到原来的二倍并将新开辟的内存空间的首地址tmp赋值给a同时更新capacity。接着便可以插入元素因为size是指向数组最后一个元素的下一个位置所以先将新元素x插到下标为size的位置然后再将size1。最后再调用AdjustUp函数进行向上调整。
调试分析 运行结果 2.6.堆的删除
堆的删除是删除堆顶的元素将堆顶的元素与最后一个元素交换然后删除数组最后一个元素再进行向下调整。
向下调整算法
当对堆进行删除时删除的往往是堆顶元素删除之后可能会破坏堆的性质这时就要进行调整。以小堆为例在删除之前首先将堆顶元素与最后一个元素交换交换完之后再将最后一个元素删除。然后从根结点开始依次向下调整直到把它调整为一个小堆。
向下调整算法的前提左右子树必须是一个堆才能调整。 调整规则
首先选出根结点的左右孩子中较小的那一个这里先假设左孩子最小然后将左孩子与右孩子进行比较若左孩子小于右孩子则不变若左孩子大于右孩子则将右孩子设为最小。然后将最小的孩子与父结点进行比较如果比父结点小则交换交换完之后把孩子结点child所在的下标赋值给父结点parent并让child指向新的父结点的左孩子然后依次向下比较直到调整到叶子结点的位置如果比父结点大则调整结束。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}
堆的删除
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);
}
在删除之前首先需要判断数组是否为空若为空则无法进行删除若不为空则可以进行删除。然后调用Swap函数将数组的第一个待删除元素与数组的最后一个元素进行交换并让size-1删除最后一个元素。最后再调用函数AdjustDown进行向下调整。
调试分析 运行结果 2.7.堆的取堆顶元素
HPDataType HeapTop(HP* php)
{//判空assert(php);//判断数组是否为空assert(php-size 0);//根结点即为堆顶元素return php-a[0];
}
在取堆顶元素之前首先要对数组进行判空操作若数组为空则无法进行读取操作若数组不为空则直接读取数组的首元素数组的首元素也就是根结点即为堆顶元素。
调试分析 运行结果 2.8.堆的判空
bool HeapEmpty(HP* php)
{//判空assert(php);//看size的大小是否为0return php-size 0;
}判断堆是否为空只需判断size是否等于0若size为0则数组为空即堆为空若size不为0则数组不为空即堆不为空。
调试分析 2.9.堆的求堆的大小
int HeapSize(HP* php)
{//判空assert(php);//size的大小即为数组的大小也就是堆的大小return php-size;
}
求堆的大小只需求数组中当前元素个数也就是求size的大小。
调试分析 三.堆的创建
3.1.向上调整建堆
向上调整建堆实际上是模拟堆的插入过程。首先将数组中的第一个元素看做是堆的根结点然后将数组中的元素依次插入堆中每插入一个元素就调用函数AdjustUp向上调整一次直到将所有的元素均插入堆中。
实现
for (int i 1; i n; i)//从第一个位置插入
{AdjustUp(a, i);
}
时间复杂度
因为堆是一棵完全二叉树而满二叉树又是一种特殊的完全二叉树为了简化计算我们不妨假设此处的堆是一棵满二叉树。 由上图得对于高度为h的满二叉树构成的堆最多进行向上调整的次数设为有 综上证得向上调整建堆的时间复杂度为O(N*logN)。
3.2.向下调整建堆
首先将数组中的元素以完全二叉树的形式排列好然后从倒数第一个非叶子结点开始调用函数AdjustDown依次向下调整。每调整一次则将i的值减1让其来到倒数第二个非叶子结点的位置重复上述操作直到i来到根结点的位置。
实现
for (int i (n - 1 - 1) / 2; i 0; i--)//n-1为最后一个结点的下标求最后一个结点的父结点的下标(n-1-1)/2
{AdjustDown(a, n, i);
}
注意
我们可以直接通过向上调整算法来建堆但是我们不可以直接通过向下调整算法来建堆。因为向下调整算法的前提左右子树必须是堆才能调整。
时间复杂度
因为堆是一棵完全二叉树而满二叉树又是一种特殊的完全二叉树为了简化计算我们不妨假设此处的堆是一棵满二叉树。 由上图得对于高度为h的满二叉树构成的堆最多进行向上调整的次数设为有 综上证得向上调整建堆的时间复杂度为O(N)。
四.堆的应用
4.1.堆排序
堆排序也就是利用堆的思想来进行排序总共分为两个步骤
建堆升序建大堆降序建小堆利用堆删除思想来进行排序 。
注意
升序也可以建小堆只是每次都要通过建堆的方式选出最小的元素。当进行第一次建堆选出最小的元素并放在数组起始位置时剩余的元素关系就会发生错乱原本的左孩子结点会变成新的根结点右孩子结点会变成新的左孩子结点。然后将剩下的元素继续进行建堆选出剩余元素中最小的元素并放入数组起始位置的下一个位置重复上述操作直到整个数组有序。整体时间复杂度为O(N^2)可见效率太低没有使用到堆的优势。因此升序要建大堆。 我们以升序建大堆为例
步骤一建堆
这里采用时间复杂度较低的向下建堆法来进行大根堆的建立。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{//建堆//建堆方式二向下调整//向下调整算法的左右子树必须是堆因此不能使用该方法直接建堆//时间复杂度O(N)//首先将数组中的元素以完全二叉树的形式排列好然后从倒数第一个非叶子结点开始依次向下调整for (int i (n - 1 - 1) / 2; i 0; i--)//n-1为最后一个结点的下标求最后一个结点的父结点的下标(n-1-1)/2{AdjustDown(a, n, i);}
}int main()
{int a[] { 27,15,19,18,28,34,65,49,25,37 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}
调试分析
建堆前 建堆后 步骤二排序
这里用到堆的删除思想。先交换数组的首尾元素此时尾结点中的元素为堆中的最大值。然后将堆的最后一个元素排除在外并继续从根结点开始对堆进行向下调整。重复上述操作直到堆中仅剩一个元素为止。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{//建堆//建堆方式二向下调整//向下调整算法的左右子树必须是堆因此不能使用该方法直接建堆//时间复杂度O(N)//首先将数组中的元素以完全二叉树的形式排列好然后从倒数第一个非叶子结点开始依次向下调整for (int i (n - 1 - 1) / 2; i 0; i--)//n-1为最后一个结点的下标求最后一个结点的父结点的下标(n-1-1)/2{AdjustDown(a, n, i);}//排序//时间复杂度O(N*logN)其中N为元素个数logN为向上调整的次数也即树的高度int end n - 1;while (end 0){//将第一个结点与最后一个结点交换Swap(a[0], a[end]);//向下调整选出次大的数AdjustDown(a, end, 0);--end;}
}int main()
{int a[] { 27,15,19,18,28,34,65,49,25,37 };HeapSort(a, sizeof(a) / sizeof(a[0]));return 0;
}
调试分析
排序前 排序后 小结
建堆和堆的删除都用到了向下调整因此掌握了向下调整就可以完成排序。
建堆的时间复杂度为O(N)排序的时间复杂度为O(N*logN)。取影响结果较大的一个也就是O(N*logN)。所以堆排序的时间复杂度为O(N*logN)。
4.2.TOP-K问题
TOP-K问题即求数据集合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 对于TOP-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
法一
堆排序采用时间复杂度最低的堆排序时间复杂度为O(N*logN)
法二
首先建立N个数的大根堆然后Top/Pop k次时间复杂度为O(Nk*logN)
注意上述两种方法在数据量非常大时是不太可取的。
法三
假设N非常大比如N是100亿而K比较小假如k是100如何求解
首先将数据集合中前k个数建立小根堆时间复杂度O(k) 然后将剩下的N-k个元素依次和堆顶元素进行比较如果比堆顶元素大就替换堆顶元素并进行向下调整 待N-k个元素依次和堆顶元素比较完之后堆中剩余的k个元素就是所求的最大的前k个元素时间复杂度O((N-k)*logk)。
注意法三较于前两种方法有很高的空间效率。
实现
//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//1.选出左右孩子中小的那一个int child parent * 2 1;//假设左孩子最小while (child size){//当右孩子存在且右孩子小于左孩子if (child 1 size a[child 1] a[child])//大堆a[child1]a[child]{child;//则将右孩子置为child}//2.小的孩子跟父亲比较如果比父亲小则交换然后继续往下调整如果比父亲大则调整结束if (a[child] a[parent])//大堆a[child]a[parent]{//交换数据Swap(a[child], a[parent]);//3.继续往下调最多调整到叶子结点就结束//把孩子的下标赋值给父亲parent child;//假设左孩子最小child parent * 2 1;}else{break;}}
}void PrintTopK(int* a, int n, int k)
{//1.建堆用a中前k个元素建堆int* kMinHeap (int*)malloc(sizeof(int) * k);assert(kMinHeap);for (int i 0; i k; i){//将a中前k的元素放进kMinHeap中kMinHeap[i] a[i];}//建立小根堆for (int i (k - 1 - 1) / 2; i 0; --i){AdjustDown(kMinHeap, k, i);}//2.将剩余的n-k个元素依次与堆顶元素比较不满则替换for (int j k; j n; j){//若后面的元素大于堆顶元素则进行替换并向下调整if (a[j] kMinHeap[0]){kMinHeap[0] a[j];AdjustDown(kMinHeap, k, 0);}}//3.打印最大的前k个元素for (int i 0; i k; i){printf(%d , kMinHeap[i]);}printf(\n);//销毁free(kMinHeap);
}void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int) * n);assert(a);srand((size_t)time(0));for (int i 0; i n; i){//产生一万个不大于100万的随机数a[i] rand() % 1000000;}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;
}
运行结果
文章转载自： http://www.morning.mqldj.cn.gov.cn.mqldj.cn http://www.morning.fqqcn.cn.gov.cn.fqqcn.cn http://www.morning.hhqtq.cn.gov.cn.hhqtq.cn http://www.morning.mjtgt.cn.gov.cn.mjtgt.cn http://www.morning.mmjyk.cn.gov.cn.mmjyk.cn http://www.morning.wkwds.cn.gov.cn.wkwds.cn http://www.morning.wskn.cn.gov.cn.wskn.cn http://www.morning.srky.cn.gov.cn.srky.cn http://www.morning.fbdkb.cn.gov.cn.fbdkb.cn http://www.morning.wfysn.cn.gov.cn.wfysn.cn http://www.morning.mwrxz.cn.gov.cn.mwrxz.cn http://www.morning.cltrx.cn.gov.cn.cltrx.cn http://www.morning.kxsnp.cn.gov.cn.kxsnp.cn http://www.morning.hhboyus.cn.gov.cn.hhboyus.cn http://www.morning.pxwzk.cn.gov.cn.pxwzk.cn http://www.morning.llqch.cn.gov.cn.llqch.cn http://www.morning.djxnw.cn.gov.cn.djxnw.cn http://www.morning.wbqk.cn.gov.cn.wbqk.cn http://www.morning.chzbq.cn.gov.cn.chzbq.cn http://www.morning.kqbwr.cn.gov.cn.kqbwr.cn http://www.morning.szoptic.com.gov.cn.szoptic.com http://www.morning.qrcxh.cn.gov.cn.qrcxh.cn http://www.morning.jwxmn.cn.gov.cn.jwxmn.cn http://www.morning.wctqc.cn.gov.cn.wctqc.cn http://www.morning.ntgsg.cn.gov.cn.ntgsg.cn http://www.morning.ymqrc.cn.gov.cn.ymqrc.cn http://www.morning.cnqwn.cn.gov.cn.cnqwn.cn http://www.morning.hrpmt.cn.gov.cn.hrpmt.cn http://www.morning.dkmzr.cn.gov.cn.dkmzr.cn http://www.morning.mjctt.cn.gov.cn.mjctt.cn http://www.morning.lsjtq.cn.gov.cn.lsjtq.cn http://www.morning.ngjpt.cn.gov.cn.ngjpt.cn http://www.morning.ljdhj.cn.gov.cn.ljdhj.cn http://www.morning.wwxg.cn.gov.cn.wwxg.cn http://www.morning.clzly.cn.gov.cn.clzly.cn http://www.morning.zxqyd.cn.gov.cn.zxqyd.cn http://www.morning.wnnlr.cn.gov.cn.wnnlr.cn http://www.morning.kbbmj.cn.gov.cn.kbbmj.cn http://www.morning.phjny.cn.gov.cn.phjny.cn http://www.morning.rjcqb.cn.gov.cn.rjcqb.cn http://www.morning.tsqrc.cn.gov.cn.tsqrc.cn http://www.morning.frtt.cn.gov.cn.frtt.cn http://www.morning.skrh.cn.gov.cn.skrh.cn http://www.morning.mmplj.cn.gov.cn.mmplj.cn http://www.morning.clybn.cn.gov.cn.clybn.cn http://www.morning.zlgbx.cn.gov.cn.zlgbx.cn http://www.morning.splkk.cn.gov.cn.splkk.cn http://www.morning.krlsz.cn.gov.cn.krlsz.cn http://www.morning.jzfrl.cn.gov.cn.jzfrl.cn http://www.morning.ygflz.cn.gov.cn.ygflz.cn http://www.morning.grnhb.cn.gov.cn.grnhb.cn http://www.morning.jxmjr.cn.gov.cn.jxmjr.cn http://www.morning.qlbmc.cn.gov.cn.qlbmc.cn http://www.morning.phjyb.cn.gov.cn.phjyb.cn http://www.morning.dbnrl.cn.gov.cn.dbnrl.cn http://www.morning.zphlb.cn.gov.cn.zphlb.cn http://www.morning.wtcyz.cn.gov.cn.wtcyz.cn http://www.morning.kstlm.cn.gov.cn.kstlm.cn http://www.morning.fjptn.cn.gov.cn.fjptn.cn http://www.morning.rlhgx.cn.gov.cn.rlhgx.cn http://www.morning.junmap.com.gov.cn.junmap.com http://www.morning.xltdh.cn.gov.cn.xltdh.cn http://www.morning.ntwxt.cn.gov.cn.ntwxt.cn http://www.morning.fnssm.cn.gov.cn.fnssm.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.ftrpvh.cn.gov.cn.ftrpvh.cn http://www.morning.tssmk.cn.gov.cn.tssmk.cn http://www.morning.fncgw.cn.gov.cn.fncgw.cn http://www.morning.ymrq.cn.gov.cn.ymrq.cn http://www.morning.ktrzt.cn.gov.cn.ktrzt.cn http://www.morning.grbgn.cn.gov.cn.grbgn.cn http://www.morning.lhxkl.cn.gov.cn.lhxkl.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.kwcnf.cn.gov.cn.kwcnf.cn http://www.morning.xmbhc.cn.gov.cn.xmbhc.cn http://www.morning.ntqlz.cn.gov.cn.ntqlz.cn http://www.morning.fhghy.cn.gov.cn.fhghy.cn http://www.morning.tfsyk.cn.gov.cn.tfsyk.cn http://www.morning.hbdqf.cn.gov.cn.hbdqf.cn http://www.morning.chkfp.cn.gov.cn.chkfp.cn
