一、本次实验环境：

腾讯云虚拟主机centos7.2上配置pyenv多版本python管理器,并安装交互式web编辑器jupyter，python版本为3.5.2，利用xshell远程ssh连接腾讯云主机，操作简易、方便。

二、对堆的简单认识：

1、堆是局部有序，且是一棵高度为O(lgN)的完全二叉树，其基本操作至多与树的高度成正比2、堆排序：非稳定排序，最好和平均时间复杂度和快速排序相当，但是最坏情况下的时间复杂度要优于快速排序，由于他对元素的操作通常在N和N之间进行，所以对于大的序列来说，两个操作数之间间隔比较远，对CPU缓存利用不太好，故速度没有快速排序快3、堆排序最显著的优点是：他是就地排序，并且其最坏情况下时间复杂度为NlogN(堆排序这里不做介绍，有兴趣的欢迎评论粘码)

4、堆可分为大根堆、小根堆：大根堆，小根堆的原理、实现请自己查阅资料，这里不做详细介绍堆与list(数组)的之间的关系：data[i].left=data[2i+1]data[i].right=data[2i+2]data[i].parent=data[(i-1)/2]大根堆：data[i]>data[i].left=data[2i+1]data[i]>data[i].right=data[2i+2]小根堆：data[i]<data[i].left=data[2i+1]data[i]<data[i].right=data[2i+2]

5、堆的应用：在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象，在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(PriorityQueue)topK，优先队列，nice，进程调度。

三、代码示例：

#1、模拟一个数据源(监控数据)不断产生数值，求一段时间内，最大的K个元素(1)、list.sort()#以da为数据源，在time=3内取得数据到lst中#并且通过lst.sort()排序#在有序的lst中截取前k个元素到ret中#函数line(k,n)，产生n行，每行k个元素importrandomimporttimeimportdatetimedefdata_source():whileTrue:yieldrandom.randint(0,10000)time.sleep(0.1)da=data_source()deftop_k1(k,time=3):start=datetime.datetime.now()lst=[]whileTrue:lst.append(next(da))current=datetime.datetime.now()if(current-start).total_seconds()>=time:start=currentlst.sort()ret=[]for_inrange(k):ret.append(lst.pop())yieldretdefline(k,n):g=top_k1(k)for_inrange(n):print(next(g))line(5,3)out：[9445,9274,9064,8732,8711][9990,9161,7938,7824,7824][9464,8897,8851,8176,8083]

(2)、插入排序#同上，这里效率更高，原因是：#在我们获取每个数据的同时就对lst进行排序(插入排序)#而上面的是把所有获得的数据进行排序importrandomimporttimeimportdatetimedefdata_source():whileTrue:yieldrandom.randint(0,10000)time.sleep(0.1)da=data_source()deftop_k2(k,time=3):start=datetime.datetime.now()lst=[]whileTrue:e=next(da)fori,vinenumerate(lst):ife<v:lst.insert(i,e)breakelse:lst.append(e)current=datetime.datetime.now()if(current-start).total_seconds()>=time:start=current#lst.sort()ret=[]for_inrange(k):ret.append(lst.pop())yieldretdefline(k,n):g=top_k2(k)for_inrange(n):print(next(g))line(5,3)out：[9619,9431,9165,9047,9041][9697,9661,9498,9043,8547][9896,9892,9539,8763,8441]

(3)、堆的实现(适合于产生大量数据的场景)#堆与list的之间的关系：#data[i].left=data[2i+1]#data[i].right=data[2i+2]#data[i].parent=data[(i-1)/2]#大根堆：#data[i]>data[i].left=data[2i+1]#data[i]>data[i].right=data[2i+2]#小根堆：#data[i]<data[i].left=data[2i+1]#data[i]<data[i].right=data[2i+2]#堆的应用：#topK#优先队列，进程调度，nice#完全依靠以上关系来实现堆#add方法：#当我们每次add一个data时，拿data和parent比较#使得在每次加入data后，生成新的大根堆#pop方法：#当我们pop出去一个元素时，把最后一个元素与之交换后#判断根、左、右，使得堆再次成为大根堆importrandomimporttimeimportdatetimedefdata_source():whileTrue:yieldrandom.randint(0,10000)time.sleep(0.1)da=data_source()defheap():data=[]#我们的数据defadd(e):idx=len(data)#最后一个元素de索引data.append(e)parent_idx=(idx-1)//2whileparent_idx>=0:#必须>=0ifdata[idx]>data[parent_idx]:data[parent_idx],data[idx]=data[idx],data[parent_idx]idx=parent_idx#交换之后data的索引parent_idx=(idx-1)//2#交换之后data的parent_idxelse:breakdefpop(idx=0):ifnotdata:returnNoneiflen(data)==1:#只有一个元素的时候returndata.pop()ret=data[idx]data[idx]=data.pop()left_idx=2*idx+1right_idx=left_idx+1whileleft_idx<len(data):#他还不是叶子节点的时候child_idx=left_idx#child_idx记录的是left和right较大的索引值ifright_idx<len(data)anddata[right_idx]>data[left_idx]:#存在右子节点child_idx=right_idx#两if分支产生的原因ifdata[idx]<data[child_idx]:#拿data和较大的比较data[idx],data[child_idx]=data[child_idx],data[idx]idx=child_idx#交换后的data的idxleft_idx=2*idx+1#重新计算data.left,data.rightright_idx=left_idx+1else:#else则她已然是大根堆breakreturnretreturnadd,popadd,pop=heap()deftop_k3(k,time=3):start=datetime.datetime.now()whileTrue:add(next(da))current=datetime.datetime.now()if(current-start).total_seconds()>=time:start=currentret=[]for_inrange(k):ret.append(pop())yieldretdefline_3(k,n):g=top_k3(k)for_inrange(n):print(next(g))line_3(5,3)out：[9702,9635,9528,9510,9254][9782,9360,9054,9040,8792][9075,8652,8602,8536,8356]#功能代码后续实现

//2、HuffmanCode(二叉树的应用，后续会示例python代码)//以下代码非递归实现，注释较少，读者只看功能原理即可，多担待#include<iostream>#include<stdio.h>#include<stdlib.h>usingnamespacestd;typedefstruct{charword;//叶子结点字符intweight;//权值intleft,right,parent;//左右子女以及双亲结点int*code;//码字}Hufftree;//创建HuffmanTreevoidCreateHuffmanTree(Hufftree*F,intn){//明白最优二叉树的原理intk1,k2;intj;for(inti=0;i<n-1;i++)//n个叶子，n-1个双亲{//找到两个双亲为-1的结点for(k1=0;k1<n+i&&F[k1].parent!=-1;k1++);for(k2=k1+1;k2<n+i&&F[k2].parent!=-1;k2++);//找到最小和次小且双亲都为-1的结点for(j=k2;j<n+i;++j){if(F[j].parent=-1){if(F[j].weight<F[k1].weight){k2=k1;k1=j;}elseif(F[j].weight<F[k2].weight)k2=j;}}F[n+i].word='X';F[n+i].weight=F[k1].weight+F[k2].weight;F[n+i].right=k1;F[n+i].left=k2;F[n+i].parent=-1;F[k1].parent=F[k2].parent=n+i;}}//创建HuffmanCodevoidCreateHuffmanCode(Hufftree*F,intn){inti,c,p;for(i=0;i<n;i++){F[i].code=(int*)malloc(n*sizeof(int));c=i;F[c].code[n-1]=0;while(F[c].parent!=-1){p=F[c].parent;if(c==F[p].right)F[i].code[F[i].code[n-1]++]=1;elseF[i].code[F[i].code[n-1]++]=0;c=p;}printf("%5d",F[i].code[n-1]);}}//输出HuffmanCodevoidPrintHuffmanCode(Hufftree*F,intn){inti,j;for(i=0;i<n;i++){cout<<F[i].word<<endl;for(j=F[i].code[n-1]-1;j>-1;j--)cout<<F[i].code[j];cout<<endl;}}intmain(void){Hufftree*F;//指向最优二叉树charch;intw;intn;//叶子总数//初始化printf("请输入叶子总数：");scanf("%d",&n);F=(Hufftree*)malloc((2*n-1)*sizeof(Hufftree));for(inti=0;i<n;i++){cout<<"请输入word：";cin>>ch;//fflush(stdin);cout<<"请输入weight：";cin>>w;F[i].word=ch;F[i].weight=w;F[i].left=F[i].right=F[i].parent=-1;}//创建HuffmanTreeCreateHuffmanTree(F,n);//创建HuffmanCodeCreateHuffmanCode(F,n);//输出HuffmanCodePrintHuffmanCode(F,n);return0;}

望各位读者多加斧正！！！