一、本次实验环境:
腾讯云虚拟主机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、堆的应用: 在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象,在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue) top K,优先队列,nice,进程调度。
三、代码示例:
#1、模拟一个数据源(监控数据)不断产生数值,求一段时间内,最大的K个元素 (1)、list.sort() #以da为数据源,在time=3内取得数据到lst中 #并且通过lst.sort()排序 #在有序的lst中截取前k个元素到ret中 #函数line(k,n),产生n行,每行k个元素 import random import time import datetime def data_source(): while True: yield random.randint(0,10000) time.sleep(0.1) da = data_source() def top_k1(k,time=3): start = datetime.datetime.now() lst = [] while True: lst.append(next(da)) current = datetime.datetime.now() if (current-start).total_seconds() >= time: start = current lst.sort() ret = [] for _ in range(k): ret.append(lst.pop()) yield ret def line(k,n): g = top_k1(k) for _ in range(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进行排序(插入排序) #而上面的是把所有获得的数据进行排序 import random import time import datetime def data_source(): while True: yield random.randint(0,10000) time.sleep(0.1) da = data_source() def top_k2(k,time=3): start = datetime.datetime.now() lst = [] while True: e = next(da) for i,v in enumerate(lst): if e < v: lst.insert(i,e) break else: lst.append(e) current = datetime.datetime.now() if (current-start).total_seconds() >= time: start = current #lst.sort() ret = [] for _ in range(k): ret.append(lst.pop()) yield ret def line(k,n): g = top_k2(k) for _ in range(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] #堆的应用: #top K #优先队列,进程调度,nice #完全依靠以上关系来实现堆 #add方法: #当我们每次add一个data时,拿data和parent比较 #使得在每次加入data后,生成新的大根堆 #pop方法: #当我们pop出去一个元素时,把最后一个元素与之交换后 #判断根、左、右,使得堆再次成为大根堆 import random import time import datetime def data_source(): while True: yield random.randint(0,10000) time.sleep(0.1) da = data_source() def heap(): data = []#我们的数据 def add(e): idx = len(data)#最后一个元素de索引 data.append(e) parent_idx = (idx - 1) // 2 while parent_idx >= 0:#必须>=0 if data[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_idx else: break def pop(idx=0): if not data: return None if len(data) == 1:#只有一个元素的时候 return data.pop() ret = data[idx] data[idx] = data.pop() left_idx = 2 * idx + 1 right_idx = left_idx + 1 while left_idx < len(data):#他还不是叶子节点的时候 child_idx = left_idx#child_idx记录的是left和right较大的索引值 if right_idx < len(data) and data[right_idx] > data[left_idx]:#存在右子节点 child_idx = right_idx#两if分支产生的原因 if data[idx] < data[child_idx]:#拿data和较大的比较 data[idx],data[child_idx] = data[child_idx],data[idx] idx = child_idx#交换后的data的idx left_idx = 2 * idx + 1#重新计算data.left,data.right right_idx = left_idx + 1 else:#else则她已然是大根堆 break return ret return add,pop add,pop = heap() def top_k3(k,time=3): start = datetime.datetime.now() while True: add(next(da)) current = datetime.datetime.now() if (current-start).total_seconds() >= time: start = current ret = [] for _ in range(k): ret.append(pop()) yield ret def line_3(k,n): g = top_k3(k) for _ in range(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> using namespace std; typedef struct { char word;//叶子结点字符 int weight;//权值 int left,right,parent;//左右子女以及双亲结点 int * code;//码字 }Hufftree; //创建HuffmanTree void CreateHuffmanTree(Hufftree * F,int n) { //明白最优二叉树的原理 int k1,k2; int j; for(int i=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; } else if(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; } } //创建HuffmanCode void CreateHuffmanCode(Hufftree * F,int n) { int i,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; else F[i].code[F[i].code[n-1]++]=0; c=p; } printf("%5d",F[i].code[n-1]); } } //输出HuffmanCode void PrintHuffmanCode(Hufftree * F,int n) { int i,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; } } int main(void) { Hufftree * F;//指向最优二叉树 char ch; int w; int n;//叶子总数 //初始化 printf("请输入叶子总数:"); scanf("%d",&n); F=(Hufftree * )malloc((2*n-1)*sizeof(Hufftree)); for(int i=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; } //创建HuffmanTree CreateHuffmanTree(F,n); //创建HuffmanCode CreateHuffmanCode(F,n); //输出HuffmanCode PrintHuffmanCode(F,n); return 0; }
望各位读者多加斧正!!!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。