溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一、本次實驗環境：
騰訊云虛擬主機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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
