响应式的学校网站,上海网站哪个比较好,珠海网站建设小小网络,360免费网站建设平台二叉树 一.二叉树的顺序结构二.堆的概念及结构三.堆的实现1.堆的结构2.堆的初始化、销毁、打印、判空3.堆中的值交换4.堆顶元素5.堆向上调整算法#xff1a;实现小堆的插入6.堆向下调整算法#xff1a;实现小堆的删除7.堆的创建1.堆向上调整算法#xff1a;建堆建堆的时间复… 二叉树 一.二叉树的顺序结构二.堆的概念及结构三.堆的实现1.堆的结构2.堆的初始化、销毁、打印、判空3.堆中的值交换4.堆顶元素5.堆向上调整算法实现小堆的插入6.堆向下调整算法实现小堆的删除7.堆的创建1.堆向上调整算法建堆建堆的时间复杂度On * logn1.堆向下调整算法建堆建堆的时间复杂度On 四.堆的应用1.TOP-K问题2.堆排序堆排序时间复杂度On * logn 一.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(完全二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
二.堆的概念及结构 堆的性质
堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。 三.堆的实现
1.堆的结构
将堆完全二叉树看作顺序表利用顺序表存储堆中的值。结构如下
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;2.堆的初始化、销毁、打印、判空
实际就是顺序表的那一套。
void HPInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}void HPDestory(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}void HPPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}3.堆中的值交换
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp *x;*x *y;*y tmp;
}4.堆顶元素
HPDataType HPTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}5.堆向上调整算法实现小堆的插入
堆的插入在已知是堆的条件下进行尾插利用堆向上调整算法使其依旧保持堆的特征。
堆向上调整算法
先将元素插入堆的末尾。插入之后如果堆的性质遭到破坏将新插入的节点顺着父亲节点往上调整到合适的位置即可。
例如先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){//小堆if (a[child] a[parent]) //大堆就是将小于号变成大于号{Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);//容量满了——扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail!);return;}php-a tmp;php-capacity newcapacity;}//尾插php-a[php-size] x;//向上调整算法AdjustUp(php-a, php-size - 1);
}6.堆向下调整算法实现小堆的删除
堆的删除在已知是堆的条件下删除堆顶的数据堆的尾删无意义依旧是堆先将堆顶与堆尾的数据进行交换再删除堆尾的数据最后利用堆向下调整算法将堆顶向下调整使其依旧保持堆的特征。
堆向下调整算法
将堆顶元素与堆中最后一个元素进行交换。删除堆中最后一个元素。将堆顶元素向下调整到满足堆特性为止。
例如现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是都是堆才能调整。 void AdjustDown(HPDataType* a, int n, int parent)
{//假设左孩子小int child 2 * parent 1;while (child n){//找出真正小的那个孩子if (child 1 n a[child 1] a[child]) //大堆就是将小于号变成大于号{child;}if (a[child] a[parent]) //大堆就是将小于号变成大于号{Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}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);
}7.堆的创建
1.堆向上调整算法建堆建堆的时间复杂度On * logn
//假设模拟php-a[] {19,34,65,18,15,28}; void AdjustUpCreateHeap(HP* php)
{//根节点不需调整从第二个节点开始调整for (int i 1; i php-size; i){AdjustUp(php-a, i);}
}
int main()
{HP hp;HPInit(hp);hp.a (HPDataType*)malloc(sizeof(HPDataType) * 6);hp.a[0] 19;hp.a[1] 34;hp.a[2] 65;hp.a[3] 18;hp.a[4] 15;hp.a[5] 28;hp.size 6;hp.capacity 6;AdjustUpCreateHeap(hp);HPPrint(hp); //15 18 28 34 19 65
}计算向上调整算法建堆时间复杂度
因为堆是完全⼆叉树而满⼆叉树也是完全⼆叉树此处为了简化使用满⼆叉树来证明(时间复杂度本来看的就是近似值多几个结点不影响最终结果) 1.堆向下调整算法建堆建堆的时间复杂度On
//假设模拟php-a[] {19,34,65,18,15,28}; void AdjustDownCreateHeap(HP* php)
{//叶子节点不需调整从倒数第一个非叶子节点开始调整for (int i (php-size - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, php-size, i);}
}
int main()
{HP hp;HPInit(hp);hp.a (HPDataType*)malloc(sizeof(HPDataType) * 6);hp.a[0] 19;hp.a[1] 34;hp.a[2] 65;hp.a[3] 18;hp.a[4] 15;hp.a[5] 28;hp.size 6;hp.capacity 6;AdjustDownCreateHeap(hp); //15 18 28 19 34 65HPPrint(hp);
}计算向下调整算法建堆时间复杂度 四.堆的应用
1.TOP-K问题
TOP-K问题即求数据个数N中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
前置知识
1 GB 1024 MB 1024*1024 KB 1024*1024*1024 Byte大约10.7亿Byte40Byte转化为GB40 / 10.7 近似3.72GB内存
问题一假设只有4GB内存要在10亿个整数中如何找出最大的前10个数
方法
建一个10亿个整数的大堆利用向下调整算法。时间复杂度O(n)进行10次TopPop取最大的前10个数。时间复杂度O(10 * logn) O(logn)10忽略不计
总时间复杂度O(n) 空间复杂度O(n)
问题二假设只有1GB内存在这些磁盘文件中取最大的前10个数。
方法
先存储1GB内存的数据再取最大前10个数依次循环4次最后在40个数据中取最大的前10个数
虽然节省了一些内存但是依旧要花费相当大的内存而且频繁的读取数据效率低。有无不需要花费多少内存就能完成的呢
问题三假设只有1KB内存在这些磁盘文件中取最大的前10个数。
方法
用数据集合中前K个元素来建堆
取前K个最大的元素则建小堆取前K个最小的元素则建大堆
时间复杂度O(k)
用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素。将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
时间复杂度O((n-k) * logk)
总时间复杂度O(n) 空间复杂度O(1)k忽略不计
代码如下
void CreateNDate()
{//写入n个数值int n 10000000;srand((unsigned int)time(NULL));//以写的方式打开文件const char* file data.txt;FILE* pf fopen(file, w);if (pf NULL){perror(fopen fail!);return;}//写数据进入文件for (int i 0; i n; i){int val (rand() i) % 10000000;fprintf(pf, %d\n, val);}//关闭文件fclose(pf);pf NULL;
}void TopK()
{//以读的方式打开文件const char* file data.txt;FILE* pf fopen(file, r);if (pf NULL){perror(fopen fail!);return;}//开K个空间为建小堆做准备int k;printf(请输入要取的最大前k个数);scanf(%d, k);int* kminheap (int*)malloc(sizeof(int) * k);if (kminheap NULL){perror(malloc fail!);return;}//读取文件中的前K个数据for (int i 0; i k; i){fscanf(pf, %d, kminheap[i]);}//建K个数的小堆向下调整算法for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(kminheap, k, i);}//取剩下的N-K个数与堆顶进行比较向下调整int val;while (fscanf(pf, %d, val) ! EOF){if (val kminheap[0]){kminheap[0] val;AdjustDown(kminheap, k, 0);}}printf(最大的前%d个数, k);for (int i 0; i k; i){printf(%d , kminheap[i]);}printf(\n);//关闭文件fclose(pf);pf NULL;
}int main()
{CreateNDate();TopK();return 0;
}2.堆排序堆排序时间复杂度On * logn
假设降序那是建小堆还是建大堆呢
结论
升序建大堆。降序建小堆。
利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
假设6个数据建小堆
已知堆顶最小可以将堆顶与队尾进行交换。向下调整保持前5个数据为小堆。循环步骤1与步骤2直到排序完成。 void HeapSort(HPDataType* a, int n)
{向上调整算法建小堆O(n*logn)//for (int i 1; i n; i)//{// AdjustUp(a, i);//}//向下调整算法建小堆O(n)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//O(n*logn)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] { 1,5,3,6,8,9,2,4,0,7 };HeapSort(a, sizeof(a) / sizeof(a[0]));for (int i 0; i sizeof(a) / sizeof(a[0]); i){printf(%d , a[i]);}printf(\n);
}堆排序时间复杂度计算 重点理解向下调整算法。
