一、本次实验环境：
腾讯云虚拟主机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;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
