数据结构之树形结构2_堆

1、数据结构之树形结构1.什么是树？复习树 树是由n(n=0)个节点构成集合。特点是任何两个节点间有且仅有一条路径。ABCDEGHFLJK根节点：没有父亲的节点。 一棵树只有一个根节点。EKJA每个节点可有0个或多个儿子节点除根节点外，每个结点有且只有一个父亲节点J和K是E的儿子节点E是J和K的父亲节点A是E的父节点没有儿子的节点称为叶节点，比如 F G H L J K 都是叶节点父亲相同的节点称为兄弟节点，比如 F G H 是兄弟节点的儿子的个数称为节点的度，比如 A 的度数为4祖先、子孙包含一个节点的所有子孙和该节点本身的集合，称为子树复习1.什么是树？2.什么是二叉树？复习1.什么是树？2.

2、什么是二叉树？3.二叉树第i层最多有多少个节点？复习1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多少个节点？4.高度为h的二叉树最多有多少个节点？复习1.什么是树？2.什么是二叉树？3.二叉树第i层最多有多少个节点？4.高度为h的二叉树最多有多少个节点？5.二叉树叶节点和度为2的节点的关系是？复习二叉树（Binary tree）二叉树就是每个节点最多只有两个子节点的树。二叉树的特点：1.第i层上最多有 个节点2.高度为h的二叉树最多有 个节点2 2i-1i-12 2h h-1-13.在非空二叉树中，叶节点的个数等于度为2的节点个数加1ABCGFJKLM复习6.什么是完全二叉树？什么是

3、满二叉树？复习二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK满二叉树除最底层外，其余各层节点都达到最大值，且最底层的节点集中在左侧的连续位置上的二叉树叫完全二叉树。ABCGFK完全二叉树复习1835627写出前序，中序，后续遍历序列前顺：1,8,5,3,6,7,2中序：8,5,1,7,6,2,3后续：5,8,7,2,6,3,1复习二叉堆(heap)二叉堆是完全二叉树任何一个节点都大于他的儿子节点的值(大根堆) 或者任何一个节点都小于他的儿子节点的值(小根堆)父子，则堆顶元素值一定最大父1）/比如5号节点的父亲是2号节点结点heapi左孩子是heap2*i，右孩子是heap2*i+

4、1 i=n/2根据堆的定义可以知道：对于大根堆：heap1最大heapih2*i且heapiheap2*i（1in / 2）大根堆heap数组下标堆用一维数组来存储，父子关系可通过数组下标快速计算出来已知下列数组表示一个堆，请画出这个堆！1238277266 4945下标 1 2 3 4 5 6 7 81234567998定理：堆的高度最大为log2(n+1)因为高度为h的二叉树最多有2h-1个节点。2h-1=n那么h=log2(n+1)怎样建堆？(小根)3建堆开始6574231387715216 3613建堆完毕数组heap初始时n=11 数组下标从第下标为n/2的节点开始，依次讨论下标为n

5、/2+1,n/2+2,.,2,1建堆的时间复杂度为详细证明见算法导论第77页，或者算法分析与设计第74页数组heap建堆完毕后1234567891011堆的向下调整(小根)void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;/把以i号节点(下标为i)为根的子树调整为堆，n为堆最后一个节点的下标(也就是数组的长度)/k表示当前节点孩子的下标/找出值最小的孩子的下标/把值最小的孩子的值赋值

6、给根/结束循环/把根的值赋值交换给孩子#define maxn 1000int heapmaxn;void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;3655231387715216 36131234567891011堆的向下调整(小根)void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+;

7、 if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;/把以i号节点(下标为i)为根的子树调整为堆，n为堆最后一个节点的下标(也就是数组的长度)/k表示当前节点孩子的下标/找出值最小的孩子的下标/把值最小的孩子的值赋值给根/结束循环/把根的值赋值交换给孩子#define maxn 1000int heapmaxn;建堆： for(i=n/2;i=1;i-)shift(i,n);调整一次堆的时间复杂度在最坏情况下是堆排序堆排序的基础选择排序堆排序的实质是利用二叉堆优化选择排序堆排序步骤：建堆。将所有节点布置成堆结构取出堆顶节点把堆尾的节

8、点移动至顶部，调整此堆跳转至2步骤，直至堆为空堆排序选择与维出堆顶节点7127 37288338 68一、取出 cout0) coutheap1; heap1=heapn-; shift(1,n);排序int heap100,t,j,n;void shift(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk;i=k; k=2*i; else break; heapi=t; int main() cinn; for(j=1;jheap j; fo

9、r(j=n/2; j=1;j-)shift(j,n); while(n0) coutheap1; heap1=heapn-; shift(1,n); return 0;例：NK宇宙班题目描述： CQNK中学高一年级总共有n(n=500000)个学生。现在你有他们的“星际语”成绩单，要从中找出“星际语”成绩最好的m(m=1000并且mn)个学生组成宇宙班，请按由高到低的顺序打印出加入于周班学生的“星际语”成绩。输入格式：第一行，两个整数n和m第二行，n个用空格间隔的整数，分别表示n个学生的“星际语”成绩输出格式：只有一行，m个空格间隔的整数，表示加入宇宙班学生的“星际语”成绩。样例输入：12 5

10、89 87 77 95 68 56 100 80 65 95 99 71样例输出：100 99 95 95 89直接对n个数由大到小排序，然后取最大的m个数取出来，时间复杂度：普通排序(冒泡、选择、插入)：O(n2+m) /一定超时快速排序:O(nlog2n+m)有没有更快的方法？1.把n个数字建成堆2.把堆顶节点的打印出来，删除堆顶元素，调整堆。 第2步重复m次。n最大为500000，219=524288,也就是log2n的值不超过19#define maxn 500001using namespace std;int heapmaxn,n,m;void shift(int i,int le

11、n) /调整成大根堆 int t=heapi,k=2*i; while(k=len) if(klen)&(heapkheapk+1)k+; /k记录值最大的孩子的编号（大根堆） if(theapk) heapi=heapk; i=k; k=2*i; else break; heapi=t;int main() int i; scanf(%d%d,&n,&m); for(i=1;i=1;i-)shift(i,n); /选出最大的m个数字 for(i=1;i=m;i+) printf(%d ,heap1); /打印堆顶元素的值，即取出最大元素 heap1=heapn; /把最后一个节点移到堆顶，相

12、当于把原来堆顶节点删了 n-; /删除堆顶节点后，总节点数减1 shift(1,n); /重新调整堆，把剩余节点中最大的值调到堆顶 return 0;堆的操作/堆的向下调整void ShiftDown(int i,int n) int k,t; t=heapi; k=2*i; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk;i=k; k=2*i; else break; heapi=t;/删除堆顶元素void Del( ) Heap1=Heapn; n-; if(n0)ShiftDown(1,n);/添加值为x的元素void Insert(

13、int x ) n+; Heapn=x; /将新元素添加在末尾 /向上调整堆/堆的向下调整void ShiftDown(int x,int n) /从编号为x的元素往下调整为小根堆 int k,t; t=heapx; k=2*x; while(k=n) if(kheapk+1)k+; if(theapk) heapx=heapk;x=k; k=2*x; else break; heapx=t;/堆的向上调整void ShiftUp(int x) /从编号为x的元素往上调整为小根堆 int t=Heapx,k=x/2; while(k0) if(tHeapk) Heapx=Heapk; x=k;

14、 k=k/2; else break; Heapx=t;特点： 不稳定 时间复杂度最坏情况下不超过 o(nlog2n)课后练手：何老板捡钻石题目描述： “欢迎来安哥拉观光，运气好能捡到钻石，运气不好就踩中地雷，看了这则旅游广告，何老板决定去安哥拉碰碰运气。到了安哥拉才发现有个坑爹的规定：游客最多只能带走n颗钻石，否则就视为走私。 何老板运气很好，他很快就搜集齐了n颗钻石，他把它们编号1到n放进了箱子。在回机场的路上，何老板发现路边还可以零星的捡到一些钻石。沿路何老板总共发现了m颗钻石，他把它们编号为n+1到n+m。何老板是个聪明人，他只会带走较重的钻石，如果捡起的钻石比箱子里的都要轻，何老板就

15、直接把它扔掉，否则他就把箱子中最轻的钻石扔了，把新捡的放进箱子。请问何老板沿途把哪些钻石从箱子里扔了出去，请按先后顺序打印出被扔出的钻石的编号。（假定每颗钻石的重量都不同，不超过int范围）。输入格式：第一行，两个空格间隔的整数n和m，(n=20000,m=100000)第二行，n个空格间隔的整数，表示已装到箱子中的n颗钻石的重量第三行，m个空格间隔的整数，表示沿途捡到的m颗钻石的重量输出格式：只有一行：若干个空格间隔的整数，表示从箱子里扔出的钻石的编号样例输入：5 58 5 9 3 74 2 1 15 8样例输出：4 6 2int main() . scanf(%d%d,&n,&m); fo

16、r(i=1;i=1;i-) ShiftDown(i,n); x=n+m; for(i=n+1;iheap1) printf(%d ,number1); heap1=heapi; number1=numberi; ShiftDown(1,n); .void ShiftDown(int i,int n) . t=heapi; y=numberi; k=i*2; while(k=n) if(kheapk+1)k+; if(theapk) heapi=heapk; numberi=numberk; i=k; k=2*i; else break; heapi=t; numberi=y; .课后作业：18

17、21 对于一给定的素数集合 S = p1, p2, ., pK,考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3.(还有其它)。该集合被称为S集合的“丑数集合”。 对于输入的集合S去寻找“丑数集合”中的第N小的“丑数”。样例：4 19 /求第19个丑数2 3 5 7 /给定的S集合结果：2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27以样例数据（2 3 5 7）为例：初始：建立一个小根堆，把数字1放入堆中；每次从堆中取出堆顶元素k，再把2k,3k, 5k, 7k放入堆中；从2开始，取出的第n个元素就是第n小的丑数；每取出一个数，插入4个数，因此任何堆里的元素是O(n)的，时间复杂度为O(4nlogn)上述解法有没有问题呢？产生了相同的数字怎么处理？比如2*3,和3*2 main( ). long long i,k,x,m,tmp,cnt=0; scanf(%I64d%I64d,&k,&m); for(i