英茗网站建设,北京效果好的网站推广,wordpress 搜索目录,郑州做网站公司排目录
1.二叉树顺序存储结构
2.堆的概念及结构
3.堆的相关接口实现
3.1 堆的插入及向上调整算法
3.1.1 向上调整算法
3.1.2 堆的插入
3.2 堆的删除及向下调整算法
3.2.1 向下调整算法
3.2.2 堆的删除
3.3 其它接口和代码实现
4.建堆或数组调堆的两种方式及复杂度分析…
目录
1.二叉树顺序存储结构
2.堆的概念及结构
3.堆的相关接口实现
3.1 堆的插入及向上调整算法
3.1.1 向上调整算法
3.1.2 堆的插入
3.2 堆的删除及向下调整算法
3.2.1 向下调整算法
3.2.2 堆的删除
3.3 其它接口和代码实现
4.建堆或数组调堆的两种方式及复杂度分析
4.1 向上调整建堆
4.1.1 建堆步骤
4.1.2 代码实现
4.1.3 时间复杂度分析 --- O(N*logN)
4.2 向下调整建堆
4.2.1 建堆步骤
4.2.2 代码实现
4.2.3 时间复杂度分析 --- O(N)
5.堆的应用
5.1 堆排序假设升序
5.1.1 堆排序步骤
5.1.2 代码实现
5.2 TopK问题
5.2.1 TopK解决步骤
5.2.2 代码实现数据从文件读取 1.二叉树顺序存储结构
顺序存储结构就是用数组来存储一般是用数组只适合来表示完全二叉树因为不是完全二叉树会有空间浪费的现象。
二叉树的顺序存储结构在物理上是一个数组在逻辑上是一个二叉树。
现实中我们通常把堆使用顺序存储结构的数组来存储而什么又是堆呢 需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 2.堆的概念及结构
其实堆就是一个完全二叉树堆中的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并且满足堆中某个结点的值总是不大于其父节点的值大堆或者堆中某个结点的值总是不小于其父节点的值小堆。
总结来说
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树 注意:所有的数组都可以表示成完全二叉树但是他并不一定是堆。
3.堆的相关接口实现 补充
对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有: 1.若i0i位置节点的双亲序号:(i-1)/2; i0i为根节点编号无双亲节点 2.若2i1 n左孩子序号:2i1若2i1n数组越界, 无左孩子
叶子就是没有左孩子也就是叶子结点的左孩子下标2i1n越界 3.若2i2 n右孩子序号:2i2; 若2i2n数组越界, 无右孩子 3.1 堆的插入及向上调整算法 先将元素插入到堆的末尾即最后一个数组元素之后插入之后如果堆的性质遭到破坏插入的结点就根据向上调整算法找到合适位置即可 3.1.1 向上调整算法
那么什么是向上调整算法呢如何实现
例如 堆[4, 27, 11, 28, 35, 19, 15, 89, 2] Push:2
图片展示
代码实现
void AdjustUp(int* 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;}}
}代码注意事项
除了插入的元素堆中的其他元素都符合堆的性质所以调整到 待调整节点和父节点 符合堆的性质即可退出调整。循环退出条件待调整节点调整到根节点 或者 待调整节点和父节点的大小关系符合堆的性质。while语句中的条件不能写parent 0因为 0-1/ 2 之后依旧是0并不符合预期的循环退出条件。如果调大堆比较符号就用;如果调小堆比较符号就用;方便以后更改。
3.1.2 堆的插入
注意:堆的物理结构是一个数组也就是用顺序表实现的插入时容量不够要记得扩容。
void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php-capacity php-size){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(HeapPush:);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}3.2 堆的删除及向下调整算法
这里堆的删除是删除堆顶数据因为只有堆顶数据才有意义堆顶数据都是最值删除堆顶后能获得次大或者次小的数
这里我们能直接删除堆顶数据吗很明显不可以根据顺序表删除数据的特点后面的元素会依次覆盖前面的元素删除堆顶数据后堆的结构就被破坏了。
其实删除思想是这样的: 将堆顶元素与堆中最后一个元素交换删除堆中最后一个元素将堆顶元素向下调整直到满足堆的结构 这种思想很巧妙在后面的堆排序中也会用到这种思想。
3.2.1 向下调整算法
代码实现
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child])child;if (a[child] a[parent]){Swap(a child, a parent);parent child;child child * 2 1;}else{break;}}
}代码注意事项
除了堆顶元素堆中的其他元素都符合堆的性质所以调整到 待调整节点和左右孩子 符合堆的性质即可退出调整。循环退出条件待调整节点调整到叶子节点 或者 待调整节点和左右孩子节点的大小关系符合堆的性质。因为要判断越界函数参数中要有数组大小size。向下调整时我们要和该结点的左右孩子中较小的那个交换。代码设计时我们可以先默认左孩子小再和右孩子进行比较得出较小的那个节点。
3.2.2 堆的删除
void HeapPop(Heap* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}3.3 其它接口和代码实现
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include time.htypedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;void Swap(int* a, int* b);
void AdjustUp(int* a, int child);//a:要调整的孩子结点所在的数组 child:要调整的孩子节点的下标
void AdjustDown(int* a, int size, int parent);//a:要调整的父亲结点所在的数组 size数组的size parent要调整的父亲节点的下标void HeapPrint(Heap* php);
void HeapInit(Heap* php);
void HeapDestory(Heap* php);
void HeapPush(Heap* php, HPDataType x);
void HeapPop(Heap* php);
HPDataType HeapTop(Heap* php);
int HeapSize(Heap* php);
int HeapEmpty(Heap* php);#include Heap.hvoid Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//调da堆
void AdjustUp(int* 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;}}
}//调da堆
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child])child;if (a[child] a[parent]){Swap(a child, a parent);parent child;child child * 2 1;}else{break;}}
}void HeapInit(Heap* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}void HeapDestory(Heap* php)
{free(php-a);php-capacity php-size 0;
}void HeapPrint(Heap* php)
{for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php-capacity php-size){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(HeapPush:);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}//这里删除的是堆顶数据只有堆顶数据才有意义
//1.swap(堆顶数据最后一个数据)
//2.删除最后一个数据
//3.堆顶数据AdjustDown
void HeapPop(Heap* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}HPDataType HeapTop(Heap* php)
{assert(php);assert(php-size 0);return php-a[0];
}int HeapSize(Heap* php)
{assert(php);return php-size;
}int HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}4.建堆或数组调堆的两种方式及复杂度分析 前面我们说过所有的数组都可以表示成完全二叉树但是他并不一定是堆。那么我们如何将这个数组调整成堆呢
我们首先会想到把数组的值依次push到堆中再把堆中数据依次赋值给数组这样就把数组调整成了堆。但是实际应用中我们不会再写一个堆这样的数据结构其次这种方式会有空间复杂度的消耗所以我们不提倡这么做。
调堆方式有两种向上调整建堆和向下调整建堆 4.1 向上调整建堆
4.1.1 建堆步骤
参考堆插入的思想数组中的每个元素都可以看做新插入的节点。
从根结点开始调整一直调整到最后一个结点。
想要调成成小堆如果该结点小于父节点就一直向上交换直到不小于其父节点或者调整到根结点。
4.1.2 代码实现
int main()
{int a[] { 27,15,19,28,35,11,4,89,2 };int size sizeof(a) / sizeof(a[0]);//这里我们建小堆//方法一向上调整算法for (int i 0; i size; i)//从根结点开始调整一直调整到最后一个结点。{AdjustUp(a, i);}for (int i 0; i size; i){printf(%d ,a[i]);}return 0;
}
4.1.3 时间复杂度分析 --- O(N*logN)
4.2 向下调整建堆
4.2.1 建堆步骤
在解释向下调整算法之前先说明一下
向下调整算法有一个前提左右子树必须是一个堆才能调整。
那么我们如何调整呢
这里我们可以利用递归思想来解决先从倒数第一个非叶子结点的子树开始调整一直调整到根结点的树。也就是倒着调整。
4.2.2 代码实现
int main()
{int a[] { 27,15,19,28,35,11,4,89,2 };int size sizeof(a) / sizeof(a[0]);//这里我们建小堆//方法二向下调整算法for (int i (size - 1 - 1) / 2; i 0; i--){AdjustDown(a, size, i);}for (int i 0; i size; i){printf(%d ,a[i]);}return 0;
}代码注意
size - 1是最后一个数组元素的下标对他减1除2后就是他父节点的下标也就是倒数第一个非叶子结点
4.2.3 时间复杂度分析 --- O(N)
总结向下调整算法建堆要比向上调整算法建堆要高效一些并且向下调整算法要更常用通常对堆顶数据进行向下调整操作所以我们一般使用向下调整来建堆。
5.堆的应用 那么我们为什么要学堆呢为什么要设计堆这种数据结构呢
主要用于解决两个问题
排序Topk问题在N个数据中找最大或者最小的前k个这里的N一般非常大 注意这里堆的应用问题和前面数组调堆的问题是同一个道理我们不能使用堆数据结构的相关接口需要在原生数组上进行操作。 5.1 堆排序假设升序
5.1.1 堆排序步骤
首先建堆这里就有一个坑了正常思维来看我们升序是建小堆因为小堆的堆顶是最小值。
我们来看看升序建小堆的效率如何
选出最小的数放在第一个位置最小的数删除后剩下的看做一个堆。但是之前建好的关系都乱了只能重新建堆才能选出次小的数。
此时的时间复杂度建堆的时间复杂度O(n)建了n次堆时间复杂度O(n*n)这种效率还不如暴力遍历排序来的直接。
这里花里胡哨的建堆选堆顶的最值进行排序结果效率和冒泡差不多显然不是我们想要的结果。 那么堆排序到底是怎么排的呢下面给出步骤 1.建堆
升序建大堆
降序建小堆
2.利用堆删除思想进行排序
1升序建的大堆堆顶是最大元素
2把堆顶最大元素和最后一个元素交换
3最后一个元素最大值不看做堆中元素堆顶元素向下调整堆顶元素就变成了次大值
4依次类推重复2~3 可以计算一下这里的时间复杂度来和上面的建小堆方法来比较一下 建大堆n次向下调整每次调整时间复杂度为O(logn),所以时间复杂度为O(n*logn) 建小堆的时间复杂度O(n*n)很显然数据非常多时这两种方法的效率是天差地别 5.1.2 代码实现
//堆排序,升序
void HeapSort(int* a, int n)
{//第一步建大堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//第二步堆删除思想进行排序依次选数调堆for (int i n - 1; i 0; i--)//最后一步交换后就一个堆顶元素最小值AdjustDown没有进行调整{//将堆顶元素和最后一个元素交换交换后最后一个元素不计入堆内Swap(a[0], a[i]);AdjustDown(a, i , 0);//这里第二个参数是数据个数最后一个元素不计入堆内正好是i}
}代码注意事项
以后我们建堆都用向下调整建堆。首先高效其次堆排序的选数调堆也用的向下调整。这里的循环变量i是最后一个元素的下标也正好是交换后数组的元素个数交换后最后一个元素不计入数组内最后一步i 1时交换后就一个堆顶元素最小值AdjustDown没有进行调整但这一步也要执行因为a[0]和a[1]要进行交换。
5.2 TopK问题
5.2.1 TopK解决步骤
Topk问题就是在N个数中找最大或者最小的前k个。这里的N一般非常大大到内存装不下
第一次碰到这个问题我们的惯性思维会去怎么解决呢
方法一先排降序前k个最大方法二N个数依次插入大堆pop k次每次取的都是堆顶数据
但是当N非常大时甚至内存都放不下很显然这两种方法不靠谱。
我们可以算一下时间复杂度
方法一O(N*logN)
方法二O(NklogN) 建堆N,k次pop klogN 我们直接来说说Topk问题的实际解决办法 用数据集合的前k个元素来建堆
前k个最大的元素建小堆
前k个最小的元素建大堆
2.用剩余的N-k个元素依次与对顶元素比较找最大小的k个比堆顶大小替换向下调整。
3.最后堆中的k个元素就是最大最小的k个数
计算时间复杂度:O(k(N-k)logk)~O(Nlogk)
5.2.2 代码实现数据从文件读取
int* TopK(int k)
{int* retArr (int*)malloc(sizeof(int) * k);//打开文件FILE* pf fopen(data,txt, r);if (pf NULL) {perror(TopK:);exit(-1); }//前k个数据读入数组for (int i 0; i k; i){fscanf(pf, %d, retArr[i]);}//数组建堆小堆for (int i (k - 2) / 2; i 0; i--){AdjustDown(retArr, k, i);}//剩余N-k个数据依次和堆顶数据比较for (int i 0; i N - k; i) {int x;fscanf(pf, %d, x);if (x retArr[0]){retArr[0] x;AdjustDown(retArr, k, 0);}}fclose(pf);return retArr;
}void testTopK()
{int* arr TopK(10);for (int i 0; i 10; i)printf(%d , arr[i]);printf(\n);free(arr);
}
