网站的设计思路范文,做网站的具体需求,百姓网招聘最新招聘信息,建筑兼职网站本章重点 二叉树的顺序结构堆的概念及结构堆的实现堆的调整算法堆的创建堆排序TOP-K问题 1.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构…本章重点 二叉树的顺序结构堆的概念及结构堆的实现堆的调整算法堆的创建堆排序TOP-K问题 1.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 访问结点的规律
//访问孩子节点
leftchild parent*21
rightchild parent*22//访问父亲结点
parent (child-1)/2
2.堆的概念及结构 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。大堆任何父亲节点 孩子结点小堆任何父亲节点 孩子结点 1.下列关键字序列为堆的是。 A 100,60,70,50,32,65 B 60,70,65,50,32,100 C 65,100,70,32,50,60 D 70,65,100,32,50,60 E 32,50,100,70,65,60 F 50,100,70,65,60,32 解析 堆Heap是一种特殊的树形数据结构它通常有两种类型小堆Min Heap和大堆Max Heap。在小堆中父节点的值小于或等于其子节点的值而在大堆中父节点的值大于或等于其子节点的值。 要判断一个序列是否是堆需要检查该序列是否满足堆的性质。我们发现A符合大堆的性质父节点的值大于或等于其子节点的值。 2.已知小根堆为8,15,10,21,34,16,12删除关键字 8 之后需重建小堆在此过程中关键字之间的比较次数是。 A 1 B 2 C 3 D 4 解析 在一个小根堆中删除根节点后需要重新构建小根堆。删除根节点后通常会将堆的最后一个元素移动到根的位置然后通过与其子节点的比较来逐级下移以确保小根堆的性质得以恢复。 给定的小根堆是8, 15, 10, 21, 34, 16, 12。 首先删除根节点8后将最后一个元素12移到根的位置得到12, 15, 10, 21, 34, 16。 然后我们需要逐级下移12直到小根堆性质得以恢复。在这个过程中我们将12与其子节点进行比较选择较小的子节点来交换位置。 第一次比较12与15比较不需要交换。 第二次比较12与10比较需要交换。 第三次比较12与16比较不需要交换。 因此关键字之间的比较次数是3次。 3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为。 A(11 5 7 2 3 17) B(11 5 7 2 17 3) C(17 11 7 2 3 5) D(17 11 7 5 3 2) E(17 7 11 3 5 2) F(17 7 11 3 2 5) 堆排序是一种基于堆数据结构的排序算法通常会建立一个最大堆Max Heap或最小堆Min Heap来进行排序。在这里我们需要建立一个最大堆。 初始堆的建立过程通常是从数组的末尾开始逐步将元素向上移动以满足堆的性质。对于给定的排序码数组(5 11 7 2 3 17)初始堆的建立步骤如下 4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是。 A[3257468] B[2357468] C[2345786] D[2345678] 3.堆的实现 这里的堆是使用数组实现的博主重点介绍堆的删除和插入接口其他接口同顺序表相同这里就不过多赘述了。
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;// 堆的初始化
void HeapInit(HP* php);
// 堆的打印
void HeapPrint(HP* php);
// 堆的销毁
void HeapDestroy(HP* php);
//堆的创建
void HeapInitArray(HP*php, int* a, int n);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的删除
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
int HeapSize(HP* php);
// 堆的判空
bool HeapEmpty(HP* php);
3.1堆的插入void HeapPush(HP* php, HPDataType x) 先将元素插入到堆的末尾即最后一个孩子之后。插入之后如果堆的性质遭到破坏将信新插入节点顺着其双亲往上调整到合适位置即可即向上调整。向上调整结束的条件是child等于0parent等于-1但是我们写的循环结束条件是child大于0因为parent的值不会是-1而是0这里可以去看我的另外一篇文章里面介绍了c语言取整规则链接 void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp *p1;*p1 *p2;*p2 temp;
}//向上调整
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 (parent - 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* temp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (temp NULL){perror(realloc fail);exit(-1);}php-a temp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUP(php-a, php-size - 1);
} 3.2堆的删除void HeapPop(HP* php) 将堆顶元素与堆中最后一个元素进行交换。删除堆中最后一个元素。将堆顶元素向下调整到满足堆特性为止。向下调整的结束条件是child等于叶子结点。 void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp *p1;*p1 *p2;*p2 temp;
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;//parent到叶子结点就结束while (child n){//可能不存在右孩子if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);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);
} 4.堆的调整算法 4.1堆向下调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37}; //向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;//parent到叶子结点就结束while (child n){//可能不存在右孩子if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}}
4.2堆向上调整算法 现在我们给出一个数组前n-1个数已经是堆了现在再添加一个数要让其满足堆的性质。我们通过从最后一个叶子结点向上调整算法可以把它调整成一个小堆。向上调整算法有一个前提前面的数据必须是一个堆才能调整。 //向上调整
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 (child - 1) / 2;}else{break;}}
}
5.堆的创建
方法一向上调整插入的思想 下面我们给出一个数组利用上面push函数的思路将数组a中的元素依次插入向上调整把第一个数当成堆满足堆向上调整的前提可以调整成堆。
int a[] {1,5,3,2,8}; //建堆
//向上调整前提是前面的数据是堆
// 思路第一个数据当作堆后面数据依次插入向上调整
//时间复杂度O(N*logN)
for (int i 1; i n; i)
{AdjustUp(a, i);
} 所以这里我们就可以给堆结合实现一个创建堆的接口使用向上调整的思路。
void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);php-a (HPDataType*)malloc(sizeof(HPDataType) * n);if (php-a NULL){perror(malloc fail);exit(-1);}php-size php-capacity n;memcpy(php-a, a, sizeof(HPDataType) * n);for (int i 0; i n; i){AdjustUp(php-a, i);}
} 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 因此建堆的时间复杂度为O(N*logN)。 方法二倒数第一个非叶子结点向下调整的思想 下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。如果根节点左右子树是堆我们可以直接向下调整即可但是此时根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树与其叶子结点开始向下调整调整完直接下标减一就是倒数的第二个非叶子节点一直调整到根节点的树就可以调整成堆。
int a[] {1,5,3,8,7,6}; //倒数第一个非叶子结点:(最后一个叶子结点-1)/2 //建堆
//向下调整建堆
//找到倒数第一个非叶子结点
//时间复杂度O(N)
for (int i (n - 1 - 1)/2; i 0; i--)
{AdjustDown(a, n, i);
}因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 因此建堆的时间复杂度为O(N)。
6.堆排序 1. 排序如何建堆
升序建大堆降序建小堆 为什么升序是建大堆呢按照我们的常理我们先建小堆然后再取出堆顶的数据这样就取得了最小的数据这样数据不就有序了为什么要去建大堆呢 取出堆顶的数据这样就取得了最小的数据然后再选次小的数此时我们只能将剩下的数看做堆但是剩下的数据还是堆嘛 此时就要重新建堆然后再取堆顶数据再建堆...每次建堆的时间复杂度N*logN一共有N个数据所以总的排序时间复杂度就是N * logN * N那还不如直接遍历一遍排序来的快呢
2. 利用堆删除思想来进行排序 所以此时我们可以建大堆将堆顶的数据和最后一个叶子结点交换由于此时的堆结构没有破坏左子树和右子树仍然是堆使用堆的向下调整去调整堆然后在缩小下次向下调整的范围也就是把最大的那个数不算做堆的范围了这样最大的数据就保存在了下标最大的位置处满足了升序的要求。每次向下调整的时间复杂度是logN一共有N个数据所以总的排序时间复杂度就是N * logN。
#define _CRT_SECURE_NO_WARNINGS 1#include stdio.hvoid Swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}
//向上调整
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 (child - 1) / 2;}else{break;}}
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;//parent到叶子结点就结束while (child n){//可能不存在右孩子if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}}
void HeapSort1(int a[],int n)
{//建堆//向上调整前提是前面的数据是堆// 思路第一个数据当作堆后面数据依次插入向上调整//O(N*logN)for (int i 1; i n; i){AdjustUp(a, i);}//升序建大堆//O(N*logN)//向下调整前提是左右子树是堆int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
void HeapSort2(int a[],int n)
{//建堆//向下调整前提是左右子树是堆// 思路找到倒数第一个非叶子结点与最后一个叶子结点进行向下调整直至根节点//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[] { 3,17,4,20,16,5 };//HeapSort1(a,sizeof(a)/sizeof(a[0]));HeapSort2(a,sizeof(a)/sizeof(a[0]));int i 0;for (i 0; i sizeof(a) / sizeof(a[0]); i){printf(%d , a[i]);}return 0;
}
运行结果 7.TOP-K问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 这里不能用大堆如果第一个数据就是最大的放在堆顶其余数据就无法入堆所以要用小堆最大的前k个数肯定比堆顶大此时该数替换堆顶的数入堆入完k个后就找到前k个最大的元素。 前k个最小的元素则建大堆 2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 3.复杂度 时间复杂度O(N*logK)空间复杂度O(K #include stdio.h
#include stdlib.h
#include string.h
#include time.h
void Swap(int* p1, int* p2)
{int temp *p1;*p1 *p2;*p2 temp;
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;//parent到叶子结点就结束while (child n){//可能不存在右孩子if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void PrintTopK(const char *filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout fopen(filename, r);if (fout NULL){perror(fopen fail);exit(-1);}int *Minheap (int*)malloc(sizeof(int) * k);if (Minheap NULL){perror(malloc fail);exit(-1);}//读文件for (int i 0; i k; i){fscanf(fout, %d, Minheap[i]);}//向下调整建小堆for (int i (k-2)/2; i 0; --i){AdjustDown(Minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int x 0;while (fscanf(fout, %d, x) ! EOF){if (x Minheap[0]){Minheap[0] x;AdjustDown(Minheap, k, 0);}}for (int i 0; i k; i){printf(%d , Minheap[i]);}printf(\n);fclose(fout);
}
void CreatNData()
{//造数据int n 10000;srand((unsigned int)time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen fail);exit(-1);}for (int i 0; i n; i){int x rand() % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}
int main()
{//CreatNData();PrintTopK(data.txt,10);return 0;
}
运行结果 但是我们怎么知道这几个数据就是前k个最大的呢我们可以在文件中手动创造10个最大的值看看输出是不是我们刚刚手动创造10个最大的值。 1000001;1000002;1000003;10000041000005; 1000006;1000007;1000008;1000009;1000009。 这样就完成了我们的TOP-K问题
文章转载自： http://www.morning.rqmr.cn.gov.cn.rqmr.cn http://www.morning.blznh.cn.gov.cn.blznh.cn http://www.morning.easiuse.com.gov.cn.easiuse.com http://www.morning.wqwbj.cn.gov.cn.wqwbj.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.qxlhj.cn.gov.cn.qxlhj.cn http://www.morning.cnqff.cn.gov.cn.cnqff.cn http://www.morning.fbqr.cn.gov.cn.fbqr.cn http://www.morning.rnpt.cn.gov.cn.rnpt.cn http://www.morning.qmzwl.cn.gov.cn.qmzwl.cn http://www.morning.ylpl.cn.gov.cn.ylpl.cn http://www.morning.pgcmz.cn.gov.cn.pgcmz.cn http://www.morning.kmkpm.cn.gov.cn.kmkpm.cn http://www.morning.mrxgm.cn.gov.cn.mrxgm.cn http://www.morning.qxltp.cn.gov.cn.qxltp.cn http://www.morning.psxcr.cn.gov.cn.psxcr.cn http://www.morning.webpapua.com.gov.cn.webpapua.com http://www.morning.qwmdx.cn.gov.cn.qwmdx.cn http://www.morning.xznrk.cn.gov.cn.xznrk.cn http://www.morning.gypcr.cn.gov.cn.gypcr.cn http://www.morning.bnxnq.cn.gov.cn.bnxnq.cn http://www.morning.kjyhh.cn.gov.cn.kjyhh.cn http://www.morning.lkbyj.cn.gov.cn.lkbyj.cn http://www.morning.rzmsl.cn.gov.cn.rzmsl.cn http://www.morning.xptkl.cn.gov.cn.xptkl.cn http://www.morning.nsppc.cn.gov.cn.nsppc.cn http://www.morning.hyjpl.cn.gov.cn.hyjpl.cn http://www.morning.jngdh.cn.gov.cn.jngdh.cn http://www.morning.dmchips.com.gov.cn.dmchips.com http://www.morning.xqffq.cn.gov.cn.xqffq.cn http://www.morning.fpqq.cn.gov.cn.fpqq.cn http://www.morning.nylbb.cn.gov.cn.nylbb.cn http://www.morning.ychoise.com.gov.cn.ychoise.com http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.bpmtq.cn.gov.cn.bpmtq.cn http://www.morning.pyncm.cn.gov.cn.pyncm.cn http://www.morning.clbgy.cn.gov.cn.clbgy.cn http://www.morning.lwnwl.cn.gov.cn.lwnwl.cn http://www.morning.mknxd.cn.gov.cn.mknxd.cn http://www.morning.frtb.cn.gov.cn.frtb.cn http://www.morning.bpmfn.cn.gov.cn.bpmfn.cn http://www.morning.sbrxm.cn.gov.cn.sbrxm.cn http://www.morning.tqqfj.cn.gov.cn.tqqfj.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.yqrfn.cn.gov.cn.yqrfn.cn http://www.morning.hxfrd.cn.gov.cn.hxfrd.cn http://www.morning.qmbgb.cn.gov.cn.qmbgb.cn http://www.morning.hkcjx.cn.gov.cn.hkcjx.cn http://www.morning.c7624.cn.gov.cn.c7624.cn http://www.morning.zlfxp.cn.gov.cn.zlfxp.cn http://www.morning.tcylt.cn.gov.cn.tcylt.cn http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.ftmly.cn.gov.cn.ftmly.cn http://www.morning.nzmw.cn.gov.cn.nzmw.cn http://www.morning.tymwx.cn.gov.cn.tymwx.cn http://www.morning.ynlpy.cn.gov.cn.ynlpy.cn http://www.morning.plhyc.cn.gov.cn.plhyc.cn http://www.morning.qrwjb.cn.gov.cn.qrwjb.cn http://www.morning.cfcdr.cn.gov.cn.cfcdr.cn http://www.morning.jgnst.cn.gov.cn.jgnst.cn http://www.morning.rgsnk.cn.gov.cn.rgsnk.cn http://www.morning.rbsmm.cn.gov.cn.rbsmm.cn http://www.morning.xmrmk.cn.gov.cn.xmrmk.cn http://www.morning.qpntn.cn.gov.cn.qpntn.cn http://www.morning.yjmlg.cn.gov.cn.yjmlg.cn http://www.morning.cjrmf.cn.gov.cn.cjrmf.cn http://www.morning.frfpx.cn.gov.cn.frfpx.cn http://www.morning.httpm.cn.gov.cn.httpm.cn http://www.morning.mspqw.cn.gov.cn.mspqw.cn http://www.morning.dfffm.cn.gov.cn.dfffm.cn http://www.morning.qsy39.cn.gov.cn.qsy39.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.clwhf.cn.gov.cn.clwhf.cn http://www.morning.pwmm.cn.gov.cn.pwmm.cn http://www.morning.lnbyk.cn.gov.cn.lnbyk.cn http://www.morning.tdmr.cn.gov.cn.tdmr.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.khdw.cn.gov.cn.khdw.cn http://www.morning.dpbgw.cn.gov.cn.dpbgw.cn http://www.morning.dbsch.cn.gov.cn.dbsch.cn
