數(shù)據(jù)結(jié)構(gòu)、算法及其應(yīng)用課件

數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用

C++描述史玉良liangyus@數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用

C++描述史玉良1堆(Heaps)左高樹(shù)(LeftistTrees)Chapter9PriorityQueues堆(Heaps)Chapter9PriorityQueu2Focus堆的實(shí)現(xiàn)1堆排序2左高樹(shù)3霍夫曼編碼4Focus堆的實(shí)現(xiàn)1堆排序2左高樹(shù)3霍夫曼編碼43與FIFO結(jié)構(gòu)的隊(duì)列不同，優(yōu)先隊(duì)列中元素出隊(duì)列的順序由元素的優(yōu)先級(jí)決定。從優(yōu)先隊(duì)列中刪除元素是根據(jù)優(yōu)先權(quán)高或低的次序，而不是元素進(jìn)入隊(duì)列的次序。例-CPU調(diào)度優(yōu)先隊(duì)列與FIFO結(jié)構(gòu)的隊(duì)列不同，優(yōu)先隊(duì)列中元素出隊(duì)列的順序由元素的4優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值。對(duì)優(yōu)先隊(duì)列執(zhí)行的操作有：查找插入一個(gè)新元素刪除優(yōu)先隊(duì)列優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值。5描述最大優(yōu)先隊(duì)列最簡(jiǎn)單的方法是采用無(wú)序線性表。假設(shè)有一個(gè)具有n個(gè)元素的優(yōu)先隊(duì)列，插入操作可以十分容易地在表的右端末尾執(zhí)行，插入所需時(shí)間為Θ(1)。刪除操作時(shí)必須查找優(yōu)先權(quán)最大的元素，即在未排序的n個(gè)元素中查找具有最大優(yōu)先權(quán)的元素，所以刪除操作所需時(shí)間為Θ(n)。優(yōu)先隊(duì)列的線性表描述描述最大優(yōu)先隊(duì)列最簡(jiǎn)單的方法是采用無(wú)序線性表。優(yōu)先隊(duì)列的線性6如果利用鏈表，插入操作在鏈頭執(zhí)行，時(shí)間為Θ(1)，而每個(gè)刪除操作所需時(shí)間為Θ(n)。優(yōu)先隊(duì)列的線性表描述如果利用鏈表，插入操作在鏈頭執(zhí)行，時(shí)間為Θ(1)，而每個(gè)刪除7另一種描述方法是采用有序線性表，當(dāng)使用公式化描述時(shí)元素按遞增次序排列，使用鏈表時(shí)則按遞減次序排列，這兩種描述方法的刪除時(shí)間均為Θ(1)，插入操作所需時(shí)間為Θ(n)。優(yōu)先隊(duì)列的線性表描述另一種描述方法是采用有序線性表，當(dāng)使用公式化描述時(shí)元素按遞增8定義：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。最大樹(shù)定義：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。9最大樹(shù)最大樹(shù)10定義：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。最小樹(shù)定義：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。11最小樹(shù)最小樹(shù)12定義：最大（最?。┑耐耆鏄?shù)。最大堆(最小堆)定義：最大（最?。┑耐耆鏄?shù)。最大堆(最小堆)13最大堆的插入最大堆的插入14插入時(shí)間復(fù)雜性插入策略從葉到根只有單一路徑，每一層的工作需耗時(shí)Θ(1)，因此實(shí)現(xiàn)此策略的時(shí)間復(fù)雜性為O(height)=O(log2n)。插入時(shí)間復(fù)雜性插入策略從葉到根只有單一路徑，每一層的工作需耗15最大堆的刪除最大堆的刪除16最大堆的刪除最大堆的刪除17刪除時(shí)間復(fù)雜性刪除策略產(chǎn)生了一條從堆的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的單一路徑，每層工作需耗時(shí)Θ(1)，因此實(shí)現(xiàn)此策略的時(shí)間復(fù)雜性為O(height)=O(log2n)。刪除時(shí)間復(fù)雜性刪除策略產(chǎn)生了一條從堆的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的單一路18開(kāi)始時(shí)堆中已經(jīng)含有n(n>0)個(gè)元素?？梢酝ㄟ^(guò)在初始為空的堆中執(zhí)行n次插入操作來(lái)構(gòu)建非空的堆，插入操作所需總時(shí)間為O(nlogn)

。最大堆的初始化開(kāi)始時(shí)堆中已經(jīng)含有n(n>0)個(gè)元素?？梢酝ㄟ^(guò)在初始為空的19更快的堆的初始化策略？思考更快的堆的初始化策略？思考20從第一個(gè)具有孩子的節(jié)點(diǎn)開(kāi)始，這個(gè)元素在數(shù)組中的位置為i=[n/2]，如果以這個(gè)元素為根的子樹(shù)已是最大堆，則此時(shí)不需調(diào)整，否則必須調(diào)整子樹(shù)使之成為堆。隨后，繼續(xù)檢查以i-1,i-2等節(jié)點(diǎn)為根的子樹(shù)，直到檢查到整個(gè)二叉樹(shù)的根節(jié)點(diǎn)（其位置為1）。思想從第一個(gè)具有孩子的節(jié)點(diǎn)開(kāi)始，這個(gè)元素在數(shù)組中的位置為i=[n21最大堆的初始化最大堆的初始化22最大堆的初始化最大堆的初始化23類MaxHeaptemplate<classT>classMaxHeap{ public: MaxHeap(intMaxHeapSize=10); ~MaxHeap(){delete[]heap;} intSize()const{returnCurrentSize;} TMax(){if(CurrentSize==0)throwOutOfBounds(); returnheap[1];} MaxHeap<T>&Insert(constT&x); MaxHeap<T>&DeleteMax(T&x); voidInitialize(Ta[],intsize,intArraySize); private: intCurrentSize,MaxSize; T*heap;//元素?cái)?shù)組};類MaxHeaptemplate<classT>24最大堆的插入template<classT>MaxHeap<T>&MaxHeap<T>::Insert(constT&x)

{//把x插入到最大堆中 if(CurrentSize==MaxSize)

throwNoMem(); //為x尋找相應(yīng)插入位置

//i從新的葉節(jié)點(diǎn)開(kāi)始，并沿著樹(shù)上升

inti=++CurrentSize；

while(i!=1&&x>heap[i/2]){ //不能把x放入heap[i]

heap[i]=heap[i/2];

i/=2; }

heap[i]=x; return*this;}最大堆的插入template<classT>25最大堆的刪除template<classT>MaxHeap<T>&MaxHeap<T>::DeleteMax(T&x)

{//將最大元素放入x，并從堆中刪除最大元素

//檢查堆是否為空 if(CurrentSize==0)

throwOutOfBounds();//隊(duì)列空

x=heap[1];//最大元素

//重構(gòu)堆

Ty=heap[CurrentSize--];//最后一個(gè)元素

//從根開(kāi)始，為y尋找合適的位置

inti=1,//堆的當(dāng)前節(jié)點(diǎn)

ci=2;//i的孩子

最大堆的刪除template<classT>26最大堆的刪除while(ci<=CurrentSize){ //heap[ci]應(yīng)該是i較大的孩子

if(ci<CurrentSize&&heap[ci]<heap[ci+1])ci++;

//能把y放入heap[i]嗎？

if(y>=heap[ci])break;//能

//不能

heap[i]=heap[ci]; i=ci; ci*=2;}heap[i]=y;return*this;}最大堆的刪除while(ci<=CurrentSize)27一棵二叉樹(shù)，它有一類特殊的節(jié)點(diǎn)叫做外部節(jié)點(diǎn)(externalnode)，用來(lái)代替樹(shù)中的空子樹(shù)，其余節(jié)點(diǎn)叫做內(nèi)部節(jié)點(diǎn)(internalnode)。增加了外部節(jié)點(diǎn)的二叉樹(shù)被稱為擴(kuò)充二叉樹(shù)(extendedbinarytree)。擴(kuò)充二叉樹(shù)一棵二叉樹(shù)，它有一類特殊的節(jié)點(diǎn)叫做外部節(jié)點(diǎn)(external28堆結(jié)構(gòu)是一種隱式數(shù)據(jù)結(jié)構(gòu)，用完全二叉樹(shù)表示的堆在數(shù)組中是隱式存貯的。由于沒(méi)有存貯結(jié)構(gòu)信息，這種描述方法空間利用率很高。盡管堆結(jié)構(gòu)的時(shí)間和空間效率都很高，但它不適合于所有優(yōu)先隊(duì)列的應(yīng)用，尤其是當(dāng)需要合并兩個(gè)優(yōu)先隊(duì)列或多個(gè)長(zhǎng)度不同的隊(duì)列時(shí)。因此需要借助于其他數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這類應(yīng)用，左高樹(shù)就能滿足這種要求。LeftistTrees(左高樹(shù))堆結(jié)構(gòu)是一種隱式數(shù)據(jù)結(jié)構(gòu)，用完全二叉樹(shù)表示的堆在數(shù)組中是隱式29擴(kuò)充二叉樹(shù)擴(kuò)充二叉樹(shù)30令s(x)為從節(jié)點(diǎn)x到它的子樹(shù)的外部節(jié)點(diǎn)的所有路徑中最短的一條，根據(jù)s(x)的定義可知，若x是外部節(jié)點(diǎn)，則s的值為0，若x為內(nèi)部節(jié)點(diǎn)，則它的s值是：

min{s(L),s(R)}+1其中L與R分別為x的左右孩子。s令s(x)為從節(jié)點(diǎn)x到它的子樹(shù)的外部節(jié)點(diǎn)的所有路徑中最短的一31擴(kuò)充二叉樹(shù)的s和w擴(kuò)充二叉樹(shù)的s和w32定義：當(dāng)且僅當(dāng)一棵二叉樹(shù)的任何一個(gè)內(nèi)部節(jié)點(diǎn)，其左孩子的s值大于等于右孩子的s值時(shí)，該二叉樹(shù)為高度優(yōu)先左高樹(shù)（height-biasedleftisttree,HBLT）。高度優(yōu)先左高樹(shù)定義：當(dāng)且僅當(dāng)一棵二叉樹(shù)的任何一個(gè)內(nèi)部節(jié)點(diǎn)，其左孩子的s33定理9-1令x為一個(gè)HBLT的內(nèi)部節(jié)點(diǎn)，則以x為根的子樹(shù)的節(jié)點(diǎn)數(shù)目至少為2s(x)-1。若子樹(shù)x有m個(gè)節(jié)點(diǎn)，s(x)最多為log2(m+1)。通過(guò)最右路徑（即，此路徑是從x開(kāi)始沿右孩子移動(dòng)）從x到達(dá)外部節(jié)點(diǎn)的路徑長(zhǎng)度為s(x)。高度優(yōu)先左高樹(shù)-性質(zhì)定理9-1令x為一個(gè)HBLT的內(nèi)部節(jié)點(diǎn)，則高度優(yōu)先左高樹(shù)-34[最大HBLT]即同時(shí)又是最大樹(shù)的HBLT；[最小HBLT]即同時(shí)又是最小樹(shù)的HBLT。最大HBLT/最小HBLT[最大HBLT]即同時(shí)又是最大樹(shù)的HBLT；最大HBLT/35插入刪除合并初始化最大HBLT的操作插入最大HBLT的操作36最大HBLT的插入操作可借助于最大HBLT的合并操作來(lái)完成。假設(shè)將元素x插入到名為H的最大HBLT中，如果建造一棵僅有一個(gè)元素x的最大HBLT然后將它與H進(jìn)行合并，結(jié)果得到的最大HBLT將包括H中的全部元素及元素x。因此插入操作只需先建立一棵僅包含欲插入元素的HBLT，然后將它與原來(lái)的HBLT合并即可。最大HBLT的插入最大HBLT的插入操作可借助于最大HBLT的合并操作來(lái)完成。37根是最大元素，如果根被刪除，將留下分別以其左右孩子為根的兩棵HBLT的子樹(shù)。將這兩棵最大HBLT合并到一起，便得到包含除刪除元素外所有元素的最大HBLT。所以刪除操作可以通過(guò)刪除根元素并對(duì)兩個(gè)子樹(shù)進(jìn)行合并來(lái)實(shí)現(xiàn)。最大HBLT的刪除根是最大元素，如果根被刪除，將留下分別以其左右孩子為根的兩棵38具有n個(gè)元素的最大HBLT，其最右路徑的長(zhǎng)度為O(logn)。合并操作僅需遍歷欲合并的HBLT的最右路徑。由于在兩條最右路徑的每個(gè)節(jié)點(diǎn)上只需耗時(shí)O(1)，因此將兩棵HBLT進(jìn)行合并具有對(duì)數(shù)復(fù)雜性。通過(guò)以上觀察，在合并算法中，僅需移動(dòng)右孩子。合并兩棵最大HBLT具有n個(gè)元素的最大HBLT，其最右路徑的長(zhǎng)度為O(logn)39合并策略最好用遞歸來(lái)實(shí)現(xiàn)。令A(yù)、B為需要合并的兩棵最大HBLT，如果其中一個(gè)為空，則將另一個(gè)作為合并的結(jié)果，因此可以假設(shè)兩者均不為空。為實(shí)現(xiàn)合并，先比較兩個(gè)根元素，較大者作為合并后的HBLT的根。假定A具有較大的根，且其左子樹(shù)為L(zhǎng)，C是由A的右子樹(shù)與B合并而成的HBLT。A與B合并所得結(jié)果即是以A的根為根，L與C為左右子樹(shù)的最大HBLT。如果L的s值小于C的s值，則C為左子樹(shù)，否則L為左子樹(shù)。合并兩棵最大HBLT合并策略最好用遞歸來(lái)實(shí)現(xiàn)。合并兩棵最大HBLT40最大HBLT的合并最大HBLT的合并41最大HBLT的合并最大HBLT的合并42通過(guò)將n個(gè)元素插入到最初為空的最大HBLT中來(lái)對(duì)其進(jìn)行初始化，所需時(shí)間為O(nlogn)。更快的方法？初始化最大HBLT通過(guò)將n個(gè)元素插入到最初為空的最大HBLT中來(lái)對(duì)其進(jìn)行初始化43為得到具有線性時(shí)間的初始化算法，首先創(chuàng)建n個(gè)最大HBLT，每個(gè)樹(shù)中僅包含n個(gè)元素中的某一個(gè)，這n棵樹(shù)排成一個(gè)FIFO隊(duì)列，然后從隊(duì)列中依次刪除兩個(gè)HBLT，將其合并，然后再加入隊(duì)列末尾，直到最后只有一棵HBLT。初始化最大HBLT為得到具有線性時(shí)間的初始化算法，首先創(chuàng)建n個(gè)最大HBLT，每44構(gòu)造五個(gè)元素：7,1,9,11,2的一棵最大HBLT。首先構(gòu)造五個(gè)單元素的最大HBLT，并形成一個(gè)FIFO隊(duì)列。例構(gòu)造五個(gè)元素：7,1,9,11,2的一棵最大HBLT。例45template<classT>voidMaxHBLT<T>::Meld(HBLTNode<T>*&x,HBLTNode<T>*y){//合并兩棵根分別為*x和*y的左高樹(shù)，返回指向新根x的指針

if(!y)return; if(!x){x=y;return;} if(x->data<y->data)Swap(x,y); Meld(x->RightChild,y); if(!x->LeftChild){x->LeftChild=x->RightChild;x->RightChild=0; x->s=1;} else{ if(x->LeftChild->s<x->RightChild->s) Swap(x->LeftChild,x->RightChild); x->s=x->RightChild->s+1;}}合并兩棵左高樹(shù)template<classT>合并兩棵左高樹(shù)46template<classT>MaxHBLT<T>&MaxHBLT<T>::DeleteMax(T&x){//刪除最大元素，并將其放入x

if(!root)throwOutOfBounds(); x=root->data;//最大元素

HBLTNode<T>*L=root->LeftChild; HBLTNode<T>*R=root->RightChild; deleteroot; root=L;

Meld(root,R); return*this;}從最大HBLT中刪除最大元素template<classT>從最大HBLT中刪除最大元47template<classT>voidMaxHBLT<T>::Initialize(Ta[],intn){//初始化有n個(gè)元素的HBLT樹(shù)

Queue<HBLTNode<T>*>Q(n); Free(root);//刪除老節(jié)點(diǎn)

//對(duì)樹(shù)的隊(duì)列進(jìn)行初始化

for(inti=1;i<=n;i++){

HBLTNode<T>*q=newHBLTNode<T>(a[i],1); Q.Add(q);} HBLTNode<T>*b,*c; for(i=1;i<=n-1;i++){Q.Delete(b).Delete(c);Meld(b,c);Q.Add(b);} if(n)Q.Delete(root);}最大HBLT的初始化template<classT>最大HBLT的初始化48堆排序(HeapSort)機(jī)器調(diào)度(MachineScheduling)霍夫曼編碼(HuffmanCodes)應(yīng)用堆排序(HeapSort)應(yīng)用49先將要排序的n個(gè)元素初始化為一個(gè)最大堆，然后每次從堆中提?。磩h除）元素。各元素將按遞減次序排列。初始化所需要的時(shí)間為(n)，每次刪除所需要的時(shí)間為O(logn)，因此總時(shí)間為O(nlogn)。堆排序先將要排序的n個(gè)元素初始化為一個(gè)最大堆，然后每次從堆中提取50template<classT>voidHeapSort(Ta[],intn){//利用堆排序算法對(duì)a[1:n]進(jìn)行排序

//創(chuàng)建一個(gè)最大堆

MaxHeap<T>H(1);H.Initialize(a,n,n); //從最大堆中逐個(gè)抽取元素

Tx; for(inti=n-1;i>=1;i--){

H.DeleteMax(x); a[i+1]=x; }

//在堆的析構(gòu)函數(shù)中保存數(shù)組a H.Deactivate(x);}堆排序算法實(shí)現(xiàn)template<classT>堆排序算法實(shí)現(xiàn)51堆排序堆排序52假設(shè)文本是由a,u,x,z組成的字符串，若這個(gè)字符串的長(zhǎng)度為1000，每個(gè)字符用一個(gè)字節(jié)來(lái)存貯，共需1000個(gè)字節(jié)（即8000位）的空間。如果每個(gè)字符用2位二進(jìn)制來(lái)編碼（00=a,01=x,10=u,11=z），則用2000位二進(jìn)制即可表示1000個(gè)字符。字符串a(chǎn)axuaxz的壓縮編碼為二進(jìn)制串0000011000011。例-壓縮假設(shè)文本是由a,u,x,z組成的字符串，若這個(gè)字符串的長(zhǎng)度為53此外，還需要一定的空間來(lái)存放編碼表，可采用如下格式來(lái)存儲(chǔ)：符號(hào)個(gè)數(shù),代碼1,符號(hào)1,代碼2,符號(hào)2,…符號(hào)個(gè)數(shù)及每個(gè)符號(hào)分別用8位二進(jìn)制來(lái)表示，每個(gè)代碼需占用[log2(符號(hào)個(gè)數(shù))]位二進(jìn)制。因此，代碼表需占用5*8+4*2=48位，壓縮比為8000/2048=3.9。例此外，還需要一定的空間來(lái)存放編碼表，可采用如下格式來(lái)存儲(chǔ)：例54字符串a(chǎn)axuaxz的壓縮編碼為二進(jìn)制串00000110000111，每個(gè)字符的編碼具有相同的位數(shù)（兩位）。從左到右依次從位串中取出2位，通過(guò)查編碼表便可獲得原字符串。例-解壓字符串a(chǎn)axuaxz的壓縮編碼為二進(jìn)制串000001100055一個(gè)字符出現(xiàn)的次數(shù)稱為頻率（frequency）在字符串a(chǎn)axuaxz中，a出現(xiàn)了三次。a,x,u,z，在這個(gè)字符串中出現(xiàn)的頻率分別為3，2，1，1。頻率一個(gè)字符出現(xiàn)的次數(shù)稱為頻率（frequency）頻率56采用可變長(zhǎng)編碼。使用編碼(0=a,10=x,110=u,111=z)。如果四個(gè)字符的出現(xiàn)頻率分別為(996,2,1,1)，則每個(gè)字符用2位編碼所得到編碼的長(zhǎng)度為2000位，而用可變長(zhǎng)編碼則僅為1006位。方案采用可變長(zhǎng)編碼。方案57可變長(zhǎng)編碼:沒(méi)有任何一個(gè)代碼是另一代碼的前綴。因此，當(dāng)從左到右檢查代碼時(shí)，可以很確定地得到與實(shí)際代碼相匹配的字符。解碼依據(jù)可變長(zhǎng)編碼:沒(méi)有任何一個(gè)代碼是另一代碼的前綴。解碼依據(jù)58可以利用擴(kuò)充二叉樹(shù)來(lái)派生一個(gè)實(shí)現(xiàn)可變長(zhǎng)編碼的特殊類，該類滿足上述前綴性質(zhì)，被稱為霍夫曼編碼?；舴蚵幋a可以利用擴(kuò)充二叉樹(shù)來(lái)派生一個(gè)實(shí)現(xiàn)可變長(zhǎng)編碼的特殊類，該類滿足59在擴(kuò)充二叉樹(shù)中，可對(duì)從根到外部節(jié)點(diǎn)的路徑進(jìn)行編碼，方法是向左孩子移動(dòng)時(shí)取0，向右孩子移動(dòng)時(shí)取1?；舴蚵幋a在擴(kuò)充二叉樹(shù)中，可對(duì)從根到外部節(jié)點(diǎn)的路徑進(jìn)行編碼，方法是向左60到節(jié)點(diǎn)(a,b,c,d,e,f)的路徑編碼分別為(00，010，011，100，101，11)霍夫曼編碼到節(jié)點(diǎn)(a,b,c,d,e,f)的路徑編碼分別為(00，0161對(duì)于一棵具有外部節(jié)點(diǎn)1，…n的擴(kuò)充二叉樹(shù)，對(duì)應(yīng)的壓縮編碼串的長(zhǎng)度為：其中L(i)為從根到達(dá)外部節(jié)點(diǎn)i的路徑長(zhǎng)度（即路徑的邊數(shù)）；F(i)為外部節(jié)點(diǎn)i的權(quán)值(壓縮中字符的頻率)；WEP為二叉樹(shù)的加權(quán)外部路徑長(zhǎng)度（weightedexternalpathlength）。加權(quán)外部路徑長(zhǎng)度對(duì)于一棵具有外部節(jié)點(diǎn)1，…n的擴(kuò)充二叉樹(shù)，對(duì)應(yīng)的壓縮編碼62若二叉樹(shù)對(duì)于給定的頻率具有最小加權(quán)外部路徑長(zhǎng)度，則這棵樹(shù)被稱為霍夫曼樹(shù)（Huffmantree）。Huffman于1952年提出?；舴蚵鼧?shù)若二叉樹(shù)對(duì)于給定的頻率具有最小加權(quán)外部路徑長(zhǎng)度，則這棵樹(shù)被稱63獲得不同字符的頻率。建立具有最小加權(quán)外部路徑的二叉樹(shù)（即霍夫曼樹(shù)），樹(shù)的外部節(jié)點(diǎn)用字符串中的字符表示，外部節(jié)點(diǎn)的權(quán)重(weight)即為該字符的頻率。遍歷從根到外部節(jié)點(diǎn)的路徑得到每個(gè)字符的編碼。用字符的編碼來(lái)代替字符串中的字符。利用霍夫曼編碼進(jìn)行壓縮獲得不同字符的頻率。利用霍夫曼編碼進(jìn)行壓縮64為了構(gòu)造霍夫曼樹(shù)，首先從僅含一個(gè)外部節(jié)點(diǎn)的二叉樹(shù)集合開(kāi)始，每個(gè)外部節(jié)點(diǎn)代表字符串中一個(gè)不同的字符，其權(quán)重等于該字符的頻率。此后不斷地從集合中選擇兩棵具有最小權(quán)重的二叉樹(shù)，并把它們合并成一棵新的二叉樹(shù)，合并方法是把這兩棵二叉樹(shù)分別作為左右子樹(shù)，然后增加一個(gè)新的根節(jié)點(diǎn)。新二叉樹(shù)的權(quán)重為兩棵子樹(shù)的權(quán)重之和。這個(gè)過(guò)程可一直持續(xù)到僅剩下一棵樹(shù)為止。構(gòu)造霍夫曼樹(shù)為了構(gòu)造霍夫曼樹(shù)，首先從僅含一個(gè)外部節(jié)點(diǎn)的二叉樹(shù)集合開(kāi)始，每65構(gòu)造霍夫曼樹(shù)構(gòu)造霍夫曼樹(shù)66權(quán)重=27。到節(jié)點(diǎn)(a,b,c,d,e,f)的路徑編碼分別為(00，010，011，100，101，11)構(gòu)造霍夫曼樹(shù)權(quán)重=27。到節(jié)點(diǎn)(a,b,c,d,e,f)的路徑編碼分別為67霍夫曼樹(shù)的建立過(guò)程可以利用最小堆來(lái)實(shí)現(xiàn)。最小堆用來(lái)存貯二叉樹(shù)集合。最小堆中的每個(gè)元素包括一棵二叉樹(shù)及其權(quán)重值。霍夫曼樹(shù)霍夫曼樹(shù)的建立過(guò)程可以利用最小堆來(lái)實(shí)現(xiàn)。霍夫曼樹(shù)68Theend!Theend!69數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用

C++描述史玉良liangyus@數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用

C++描述史玉良70堆(Heaps)左高樹(shù)(LeftistTrees)Chapter9PriorityQueues堆(Heaps)Chapter9PriorityQueu71Focus堆的實(shí)現(xiàn)1堆排序2左高樹(shù)3霍夫曼編碼4Focus堆的實(shí)現(xiàn)1堆排序2左高樹(shù)3霍夫曼編碼472與FIFO結(jié)構(gòu)的隊(duì)列不同，優(yōu)先隊(duì)列中元素出隊(duì)列的順序由元素的優(yōu)先級(jí)決定。從優(yōu)先隊(duì)列中刪除元素是根據(jù)優(yōu)先權(quán)高或低的次序，而不是元素進(jìn)入隊(duì)列的次序。例-CPU調(diào)度優(yōu)先隊(duì)列與FIFO結(jié)構(gòu)的隊(duì)列不同，優(yōu)先隊(duì)列中元素出隊(duì)列的順序由元素的73優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值。對(duì)優(yōu)先隊(duì)列執(zhí)行的操作有：查找插入一個(gè)新元素刪除優(yōu)先隊(duì)列優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值。74描述最大優(yōu)先隊(duì)列最簡(jiǎn)單的方法是采用無(wú)序線性表。假設(shè)有一個(gè)具有n個(gè)元素的優(yōu)先隊(duì)列，插入操作可以十分容易地在表的右端末尾執(zhí)行，插入所需時(shí)間為Θ(1)。刪除操作時(shí)必須查找優(yōu)先權(quán)最大的元素，即在未排序的n個(gè)元素中查找具有最大優(yōu)先權(quán)的元素，所以刪除操作所需時(shí)間為Θ(n)。優(yōu)先隊(duì)列的線性表描述描述最大優(yōu)先隊(duì)列最簡(jiǎn)單的方法是采用無(wú)序線性表。優(yōu)先隊(duì)列的線性75如果利用鏈表，插入操作在鏈頭執(zhí)行，時(shí)間為Θ(1)，而每個(gè)刪除操作所需時(shí)間為Θ(n)。優(yōu)先隊(duì)列的線性表描述如果利用鏈表，插入操作在鏈頭執(zhí)行，時(shí)間為Θ(1)，而每個(gè)刪除76另一種描述方法是采用有序線性表，當(dāng)使用公式化描述時(shí)元素按遞增次序排列，使用鏈表時(shí)則按遞減次序排列，這兩種描述方法的刪除時(shí)間均為Θ(1)，插入操作所需時(shí)間為Θ(n)。優(yōu)先隊(duì)列的線性表描述另一種描述方法是采用有序線性表，當(dāng)使用公式化描述時(shí)元素按遞增77定義：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。最大樹(shù)定義：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。78最大樹(shù)最大樹(shù)79定義：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。最小樹(shù)定義：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)（如果有的話）值的樹(shù)。80最小樹(shù)最小樹(shù)81定義：最大（最?。┑耐耆鏄?shù)。最大堆(最小堆)定義：最大（最?。┑耐耆鏄?shù)。最大堆(最小堆)82最大堆的插入最大堆的插入83插入時(shí)間復(fù)雜性插入策略從葉到根只有單一路徑，每一層的工作需耗時(shí)Θ(1)，因此實(shí)現(xiàn)此策略的時(shí)間復(fù)雜性為O(height)=O(log2n)。插入時(shí)間復(fù)雜性插入策略從葉到根只有單一路徑，每一層的工作需耗84最大堆的刪除最大堆的刪除85最大堆的刪除最大堆的刪除86刪除時(shí)間復(fù)雜性刪除策略產(chǎn)生了一條從堆的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的單一路徑，每層工作需耗時(shí)Θ(1)，因此實(shí)現(xiàn)此策略的時(shí)間復(fù)雜性為O(height)=O(log2n)。刪除時(shí)間復(fù)雜性刪除策略產(chǎn)生了一條從堆的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的單一路87開(kāi)始時(shí)堆中已經(jīng)含有n(n>0)個(gè)元素?？梢酝ㄟ^(guò)在初始為空的堆中執(zhí)行n次插入操作來(lái)構(gòu)建非空的堆，插入操作所需總時(shí)間為O(nlogn)

。最大堆的初始化開(kāi)始時(shí)堆中已經(jīng)含有n(n>0)個(gè)元素?？梢酝ㄟ^(guò)在初始為空的88更快的堆的初始化策略？思考更快的堆的初始化策略？思考89從第一個(gè)具有孩子的節(jié)點(diǎn)開(kāi)始，這個(gè)元素在數(shù)組中的位置為i=[n/2]，如果以這個(gè)元素為根的子樹(shù)已是最大堆，則此時(shí)不需調(diào)整，否則必須調(diào)整子樹(shù)使之成為堆。隨后，繼續(xù)檢查以i-1,i-2等節(jié)點(diǎn)為根的子樹(shù)，直到檢查到整個(gè)二叉樹(shù)的根節(jié)點(diǎn)（其位置為1）。思想從第一個(gè)具有孩子的節(jié)點(diǎn)開(kāi)始，這個(gè)元素在數(shù)組中的位置為i=[n90最大堆的初始化最大堆的初始化91最大堆的初始化最大堆的初始化92類MaxHeaptemplate<classT>classMaxHeap{ public: MaxHeap(intMaxHeapSize=10); ~MaxHeap(){delete[]heap;} intSize()const{returnCurrentSize;} TMax(){if(CurrentSize==0)throwOutOfBounds(); returnheap[1];} MaxHeap<T>&Insert(constT&x); MaxHeap<T>&DeleteMax(T&x); voidInitialize(Ta[],intsize,intArraySize); private: intCurrentSize,MaxSize; T*heap;//元素?cái)?shù)組};類MaxHeaptemplate<classT>93最大堆的插入template<classT>MaxHeap<T>&MaxHeap<T>::Insert(constT&x)

{//把x插入到最大堆中 if(CurrentSize==MaxSize)

throwNoMem(); //為x尋找相應(yīng)插入位置

//i從新的葉節(jié)點(diǎn)開(kāi)始，并沿著樹(shù)上升

inti=++CurrentSize；

while(i!=1&&x>heap[i/2]){ //不能把x放入heap[i]

heap[i]=heap[i/2];

i/=2; }

heap[i]=x; return*this;}最大堆的插入template<classT>94最大堆的刪除template<classT>MaxHeap<T>&MaxHeap<T>::DeleteMax(T&x)

{//將最大元素放入x，并從堆中刪除最大元素

//檢查堆是否為空 if(CurrentSize==0)

throwOutOfBounds();//隊(duì)列空

x=heap[1];//最大元素

//重構(gòu)堆

Ty=heap[CurrentSize--];//最后一個(gè)元素

//從根開(kāi)始，為y尋找合適的位置

inti=1,//堆的當(dāng)前節(jié)點(diǎn)

ci=2;//i的孩子

最大堆的刪除template<classT>95最大堆的刪除while(ci<=CurrentSize){ //heap[ci]應(yīng)該是i較大的孩子

if(ci<CurrentSize&&heap[ci]<heap[ci+1])ci++;

//能把y放入heap[i]嗎？

if(y>=heap[ci])break;//能

//不能

heap[i]=heap[ci]; i=ci; ci*=2;}heap[i]=y;return*this;}最大堆的刪除while(ci<=CurrentSize)96一棵二叉樹(shù)，它有一類特殊的節(jié)點(diǎn)叫做外部節(jié)點(diǎn)(externalnode)，用來(lái)代替樹(shù)中的空子樹(shù)，其余節(jié)點(diǎn)叫做內(nèi)部節(jié)點(diǎn)(internalnode)。增加了外部節(jié)點(diǎn)的二叉樹(shù)被稱為擴(kuò)充二叉樹(shù)(extendedbinarytree)。擴(kuò)充二叉樹(shù)一棵二叉樹(shù)，它有一類特殊的節(jié)點(diǎn)叫做外部節(jié)點(diǎn)(external97堆結(jié)構(gòu)是一種隱式數(shù)據(jù)結(jié)構(gòu)，用完全二叉樹(shù)表示的堆在數(shù)組中是隱式存貯的。由于沒(méi)有存貯結(jié)構(gòu)信息，這種描述方法空間利用率很高。盡管堆結(jié)構(gòu)的時(shí)間和空間效率都很高，但它不適合于所有優(yōu)先隊(duì)列的應(yīng)用，尤其是當(dāng)需要合并兩個(gè)優(yōu)先隊(duì)列或多個(gè)長(zhǎng)度不同的隊(duì)列時(shí)。因此需要借助于其他數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這類應(yīng)用，左高樹(shù)就能滿足這種要求。LeftistTrees(左高樹(shù))堆結(jié)構(gòu)是一種隱式數(shù)據(jù)結(jié)構(gòu)，用完全二叉樹(shù)表示的堆在數(shù)組中是隱式98擴(kuò)充二叉樹(shù)擴(kuò)充二叉樹(shù)99令s(x)為從節(jié)點(diǎn)x到它的子樹(shù)的外部節(jié)點(diǎn)的所有路徑中最短的一條，根據(jù)s(x)的定義可知，若x是外部節(jié)點(diǎn)，則s的值為0，若x為內(nèi)部節(jié)點(diǎn)，則它的s值是：

min{s(L),s(R)}+1其中L與R分別為x的左右孩子。s令s(x)為從節(jié)點(diǎn)x到它的子樹(shù)的外部節(jié)點(diǎn)的所有路徑中最短的一100擴(kuò)充二叉樹(shù)的s和w擴(kuò)充二叉樹(shù)的s和w101定義：當(dāng)且僅當(dāng)一棵二叉樹(shù)的任何一個(gè)內(nèi)部節(jié)點(diǎn)，其左孩子的s值大于等于右孩子的s值時(shí)，該二叉樹(shù)為高度優(yōu)先左高樹(shù)（height-biasedleftisttree,HBLT）。高度優(yōu)先左高樹(shù)定義：當(dāng)且僅當(dāng)一棵二叉樹(shù)的任何一個(gè)內(nèi)部節(jié)點(diǎn)，其左孩子的s102定理9-1令x為一個(gè)HBLT的內(nèi)部節(jié)點(diǎn)，則以x為根的子樹(shù)的節(jié)點(diǎn)數(shù)目至少為2s(x)-1。若子樹(shù)x有m個(gè)節(jié)點(diǎn)，s(x)最多為log2(m+1)。通過(guò)最右路徑（即，此路徑是從x開(kāi)始沿右孩子移動(dòng)）從x到達(dá)外部節(jié)點(diǎn)的路徑長(zhǎng)度為s(x)。高度優(yōu)先左高樹(shù)-性質(zhì)定理9-1令x為一個(gè)HBLT的內(nèi)部節(jié)點(diǎn)，則高度優(yōu)先左高樹(shù)-103[最大HBLT]即同時(shí)又是最大樹(shù)的HBLT；[最小HBLT]即同時(shí)又是最小樹(shù)的HBLT。最大HBLT/最小HBLT[最大HBLT]即同時(shí)又是最大樹(shù)的HBLT；最大HBLT/104插入刪除合并初始化最大HBLT的操作插入最大HBLT的操作105最大HBLT的插入操作可借助于最大HBLT的合并操作來(lái)完成。假設(shè)將元素x插入到名為H的最大HBLT中，如果建造一棵僅有一個(gè)元素x的最大HBLT然后將它與H進(jìn)行合并，結(jié)果得到的最大HBLT將包括H中的全部元素及元素x。因此插入操作只需先建立一棵僅包含欲插入元素的HBLT，然后將它與原來(lái)的HBLT合并即可。最大HBLT的插入最大HBLT的插入操作可借助于最大HBLT的合并操作來(lái)完成。106根是最大元素，如果根被刪除，將留下分別以其左右孩子為根的兩棵HBLT的子樹(shù)。將這兩棵最大HBLT合并到一起，便得到包含除刪除元素外所有元素的最大HBLT。所以刪除操作可以通過(guò)刪除根元素并對(duì)兩個(gè)子樹(shù)進(jìn)行合并來(lái)實(shí)現(xiàn)。最大HBLT的刪除根是最大元素，如果根被刪除，將留下分別以其左右孩子為根的兩棵107具有n個(gè)元素的最大HBLT，其最右路徑的長(zhǎng)度為O(logn)。合并操作僅需遍歷欲合并的HBLT的最右路徑。由于在兩條最右路徑的每個(gè)節(jié)點(diǎn)上只需耗時(shí)O(1)，因此將兩棵HBLT進(jìn)行合并具有對(duì)數(shù)復(fù)雜性。通過(guò)以上觀察，在合并算法中，僅需移動(dòng)右孩子。合并兩棵最大HBLT具有n個(gè)元素的最大HBLT，其最右路徑的長(zhǎng)度為O(logn)108合并策略最好用遞歸來(lái)實(shí)現(xiàn)。令A(yù)、B為需要合并的兩棵最大HBLT，如果其中一個(gè)為空，則將另一個(gè)作為合并的結(jié)果，因此可以假設(shè)兩者均不為空。為實(shí)現(xiàn)合并，先比較兩個(gè)根元素，較大者作為合并后的HBLT的根。假定A具有較大的根，且其左子樹(shù)為L(zhǎng)，C是由A的右子樹(shù)與B合并而成的HBLT。A與B合并所得結(jié)果即是以A的根為根，L與C為左右子樹(shù)的最大HBLT。如果L的s值小于C的s值，則C為左子樹(shù)，否則L為左子樹(shù)。合并兩棵最大HBLT合并策略最好用遞歸來(lái)實(shí)現(xiàn)。合并兩棵最大HBLT109最大HBLT的合并最大HBLT的合并110最大HBLT的合并最大HBLT的合并111通過(guò)將n個(gè)元素插入到最初為空的最大HBLT中來(lái)對(duì)其進(jìn)行初始化，所需時(shí)間為O(nlogn)。更快的方法？初始化最大HBLT通過(guò)將n個(gè)元素插入到最初為空的最大HBLT中來(lái)對(duì)其進(jìn)行初始化112為得到具有線性時(shí)間的初始化算法，首先創(chuàng)建n個(gè)最大HBLT，每個(gè)樹(shù)中僅包含n個(gè)元素中的某一個(gè)，這n棵樹(shù)排成一個(gè)FIFO隊(duì)列，然后從隊(duì)列中依次刪除兩個(gè)HBLT，將其合并，然后再加入隊(duì)列末尾，直到最后只有一棵HBLT。初始化最大HBLT為得到具有線性時(shí)間的初始化算法，首先創(chuàng)建n個(gè)最大HBLT，每113構(gòu)造五個(gè)元素：7,1,9,11,2的一棵最大HBLT。首先構(gòu)造五個(gè)單元素的最大HBLT，并形成一個(gè)FIFO隊(duì)列。例構(gòu)造五個(gè)元素：7,1,9,11,2的一棵最大HBLT。例114template<classT>voidMaxHBLT<T>::Meld(HBLTNode<T>*&x,HBLTNode<T>*y){//合并兩棵根分別為*x和*y的左高樹(shù)，返回指向新根x的指針

if(!y)return; if(!x){x=y;return;} if(x->data<y->data)Swap(x,y); Meld(x->RightChild,y); if(!x->LeftChild){x->LeftChild=x->RightChild;x->RightChild=0; x->s=1;} else{ if(x->LeftChild->s<x->RightChild->s) Swap(x->LeftChild,x->RightChild); x->s=x->RightChild->s+1;}}合并兩棵左高樹(shù)template<classT>合并兩棵左高樹(shù)115template<classT>MaxHBLT<T>&MaxHBLT<T>::DeleteMax(T&x){//刪除最大元素，并將其放入x

if(!root)throwOutOfBounds(); x=root->data;//最大元素

HBLTNode<T>*L=root->LeftChild; HBLTNode<T>*R=root->RightChild; deleteroot; root=L;

Meld(root,R); return*this;}從最大HBLT中刪除最大元素template<classT>從最大HBLT中刪除最大元116template<classT>voidMaxHBLT<T>::Initialize(Ta[],intn){//初始化有n個(gè)元素的HBLT樹(shù)

Queue<HBLTNode<T>*>Q(n); Free(root);//刪除老節(jié)點(diǎn)

//對(duì)樹(shù)的隊(duì)列進(jìn)行初始化

for(inti=1;i<=n;i++){

HBLTNode<T>*q=newHBLTNode<T>(a[i],1); Q.Add(q);} HBLTNode<T>*b,*c; for(i=1;i<=n-1;i++){Q.Delete(b).Delete(c);Meld(b,c);Q.Add(b);} if(n)Q.Delete(root);}最大HBLT的初始化template<classT>最大HBLT的初始化117堆排序(HeapSort)機(jī)器調(diào)度(MachineScheduling)霍夫曼編碼(HuffmanCodes)應(yīng)用堆排序(HeapSort)應(yīng)用118先將要排序的n個(gè)元素初始化為一個(gè)最大堆，然后每次從堆中提?。磩h除）元素。各元素將按遞減次序排列。初始化所需要的時(shí)間為(n)，每次刪除所需要的時(shí)間為O(logn)，因此總時(shí)間為O(nlogn)。堆排序先將要排序的n個(gè)元素初始化為一個(gè)最大堆，然后每次從堆中提取119template<classT>voidHeapSort(Ta[],intn){//利用堆排序算法對(duì)a[1:n]進(jìn)行排序

//創(chuàng)建一個(gè)最大堆

MaxHeap<T>H(1);H.Initialize(a,n,n); //從最大堆中逐個(gè)抽取元素

Tx; for(inti=n-1;i>=1;i--){

H.DeleteMax(x); a[i+1]=x; }

//在堆的析構(gòu)函數(shù)中保存數(shù)組a H.Deactivate(x);}堆排序算法實(shí)現(xiàn)template<classT>堆排序算法實(shí)現(xiàn)120堆排序堆排序121假設(shè)文本是由a,u,x,z組成的字符串，若這個(gè)字符串的長(zhǎng)度為1000，每個(gè)字符用一個(gè)字節(jié)來(lái)存貯，共需1000個(gè)字節(jié)（即8000位）的空間。如果每個(gè)字符用2位二進(jìn)制來(lái)編碼（00=a,01=x,10=u,11=z），則用2000位二進(jìn)制即可表示1000個(gè)字符。字符串a(chǎn)axuaxz的壓縮編碼為二進(jìn)制串0000011000011。例-壓縮假設(shè)文本是由a,u,x,z組成的字符串，若這個(gè)字符串的長(zhǎng)度為122此外，還需要一定的空間來(lái)存放編碼表，可采用如下格式來(lái)存儲(chǔ)：符號(hào)個(gè)數(shù),代碼1,符號(hào)1