1、數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+描述描述22n 堆(Heaps)n 左高樹(Leftist Trees)Chapter9 Priority QueuesChapter9 Priority Queues33FocusFocus堆的實(shí)現(xiàn)堆的實(shí)現(xiàn)1堆排序堆排序2左高樹左高樹3霍夫曼編碼霍夫曼編碼444與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ì)列優(yōu)先隊(duì)列55優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值。對(duì)優(yōu)先隊(duì)列執(zhí)行的操作有：查找插入一個(gè)新元素刪除優(yōu)先隊(duì)列

2、優(yōu)先隊(duì)列66描述最大優(yōu)先隊(duì)列最簡單的方法是采用無序線性表。假設(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ì)列的線性表描述77如果利用鏈表，插入操作在鏈頭執(zhí)行，時(shí)間為(1)，而每個(gè)刪除操作所需時(shí)間為(n)。優(yōu)先隊(duì)列的線性表描述優(yōu)先隊(duì)列的線性表描述88另一種描述方法是采用有序線性表，當(dāng)使用公式化描述時(shí)元素按遞增次序排列，使用鏈表時(shí)則按遞減次序排列，這兩種描述方法的刪除時(shí)間均為(1)，插入操作所需時(shí)間為(n)。優(yōu)

3、先隊(duì)列的線性表描述優(yōu)先隊(duì)列的線性表描述99定義：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)（如果有的話）值的樹。最大樹最大樹1010最大樹最大樹1111定義：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)（如果有的話）值的樹。最小樹最小樹1212最小樹最小樹1313定義：最大（最?。┑耐耆鏄洹Ｗ畲蠖炎畲蠖? (最小堆最小堆) )1414最大堆的插入最大堆的插入1515插入時(shí)間復(fù)雜性插入時(shí)間復(fù)雜性n插入策略從葉到根只有單一路徑，每一層的工作需耗時(shí)(1)，因此實(shí)現(xiàn)此策略的時(shí)間復(fù)雜性為O(height)=O(log2n)。1616最大堆的刪除最大堆的刪除1717最大堆的刪除最大堆的刪除1818刪除時(shí)間復(fù)雜性刪除時(shí)間復(fù)雜

4、性n刪除策略產(chǎn)生了一條從堆的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的單一路徑，每層工作需耗時(shí)(1)，因此實(shí)現(xiàn)此策略的時(shí)間復(fù)雜性為O(height)=O(log2n)。1919開始時(shí)堆中已經(jīng)含有n(n0) 個(gè)元素?？梢酝ㄟ^在初始為空的堆中執(zhí)行n次插入操作來構(gòu)建非空的堆，插入操作所需總時(shí)間為O(nlogn) 。最大堆的初始化最大堆的初始化2020更快的堆的初始化策略？思考思考2121從第一個(gè)具有孩子的節(jié)點(diǎn)開始，這個(gè)元素在數(shù)組中的位置為i=n/2，如果以這個(gè)元素為根的子樹已是最大堆，則此時(shí)不需調(diào)整，否則必須調(diào)整子樹使之成為堆。隨后，繼續(xù)檢查以i-1,i-2等節(jié)點(diǎn)為根的子樹，直到檢查到整個(gè)二叉樹的根節(jié)點(diǎn)（其位置為1）。思想思

5、想2222最大堆的初始化最大堆的初始化2323最大堆的初始化最大堆的初始化2424類類MaxHeapMaxHeaptemplateclass MaxHeap public :MaxHeap(int MaxHeapSize = 10);MaxHeap() delete heap;int Size() const return CurrentSize;T Max() if (CurrentSize = 0) throw OutOfBounds();return heap1;MaxHeap& Insert(const T& x);MaxHeap& DeleteMax(T&am

6、p; x);void Initialize(T a, int size, int ArraySize);private :int CurrentSize, MaxSize;T *heap; / 元素?cái)?shù)組 ;2525最大堆的插入最大堆的插入templateMaxHeap& MaxHeap:Insert(const T& x) /把x插入到最大堆中if (CurrentSize=MaxSize) throw NoMem();/為x尋找相應(yīng)插入位置 /i從新的葉節(jié)點(diǎn)開始，并沿著樹上升int i=+CurrentSize；while (i!=1 & xheapi/2) /不能把

7、x放入heapiheapi=heapi/2;i/=2; heapi=x;return *this; 2626最大堆的刪除最大堆的刪除templateMaxHeap& MaxHeap:DeleteMax(T& x) /將最大元素放入x，并從堆中刪除最大元素/檢查堆是否為空if (CurrentSize=0) throw OutOfBounds(); /隊(duì)列空x=heap1;/最大元素/重構(gòu)堆T y=heapCurrentSize-;/最后一個(gè)元素/從根開始，為y尋找合適的位置int i=1, /堆的當(dāng)前節(jié)點(diǎn) ci=2;/i的孩子2727最大堆的刪除最大堆的刪除while (ci=

8、CurrentSize) /heapci應(yīng)該是i較大的孩子if(ciCurrentSize & heapci=heapci) break; /能 /不能heapi=heapci;i=ci;ci*=2; heapi=y;return *this; 2828一棵二叉樹，它有一類特殊的節(jié)點(diǎn)叫做外部節(jié)點(diǎn)(external node)，用來代替樹中的空子樹，其余節(jié)點(diǎn)叫做內(nèi)部節(jié)點(diǎn)(internal node)。增加了外部節(jié)點(diǎn)的二叉樹被稱為擴(kuò)充二叉樹(extended binary tree)。擴(kuò)充二叉樹擴(kuò)充二叉樹2929堆結(jié)構(gòu)是一種隱式數(shù)據(jù)結(jié)構(gòu)，用完全二叉樹表示的堆在數(shù)組中是隱式存貯的。由于沒有存

9、貯結(jié)構(gòu)信息，這種描述方法空間利用率很高。盡管堆結(jié)構(gòu)的時(shí)間和空間效率都很高，但它不適合于所有優(yōu)先隊(duì)列的應(yīng)用，尤其是當(dāng)需要合并兩個(gè)優(yōu)先隊(duì)列或多個(gè)長度不同的隊(duì)列時(shí)。因此需要借助于其他數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)這類應(yīng)用，左高樹就能滿足這種要求。Leftist Trees(Leftist Trees(左高樹左高樹) )3030擴(kuò)充二叉樹擴(kuò)充二叉樹3131令s(x)為從節(jié)點(diǎn)x到它的子樹的外部節(jié)點(diǎn)的所有路徑中最短的一條，根據(jù)s(x)的定義可知，若x是外部節(jié)點(diǎn)，則s的值為0，若x為內(nèi)部節(jié)點(diǎn)，則它的s值是： mins(L),s(R) + 1其中L與R分別為x 的左右孩子。s s3232擴(kuò)充二叉樹的擴(kuò)充二叉樹的s s和和w

10、w3333定義：當(dāng)且僅當(dāng)一棵二叉樹的任何一個(gè)內(nèi)部節(jié)點(diǎn)，其左孩子的 s 值大于等于右孩子的 s 值時(shí)，該二叉樹為高度優(yōu)先左高樹（height-biased leftist tree, HBLT）。高度優(yōu)先左高樹高度優(yōu)先左高樹3434定理9-1 令x為一個(gè)HBLT的內(nèi)部節(jié)點(diǎn)，則n 以x為根的子樹的節(jié)點(diǎn)數(shù)目至少為2s(x)-1。n 若子樹x有m個(gè)節(jié)點(diǎn)，s(x)最多為log2(m+1)。1. 通過最右路徑（即，此路徑是從x 開始沿右孩子移動(dòng)）從x到達(dá)外部節(jié)點(diǎn)的路徑長度為s(x)。高度優(yōu)先左高樹高度優(yōu)先左高樹- -性質(zhì)性質(zhì)3535最大HBLT 即同時(shí)又是最大樹的HBLT；最小HBLT 即同時(shí)又是最小樹的

11、HBLT。最大最大HBLT/HBLT/最小最小HBLTHBLT3636n 插入n 刪除n 合并n 初始化最大最大HBLTHBLT的操作的操作3737最大HBLT的插入操作可借助于最大HBLT的合并操作來完成。假設(shè)將元素x插入到名為H的最大HBLT中，如果建造一棵僅有一個(gè)元素x的最大HBLT然后將它與H進(jìn)行合并，結(jié)果得到的最大HBLT將包括H中的全部元素及元素x。因此插入操作只需先建立一棵僅包含欲插入元素的HBLT，然后將它與原來的HBLT合并即可。最大最大HBLTHBLT的插入的插入3838根是最大元素，如果根被刪除，將留下分別以其左右孩子為根的兩棵HBLT的子樹。將這兩棵最大HBLT合并到一

12、起，便得到包含除刪除元素外所有元素的最大HBLT。所以刪除操作可以通過刪除根元素并對(duì)兩個(gè)子樹進(jìn)行合并來實(shí)現(xiàn)。最大最大HBLTHBLT的刪除的刪除3939具有n個(gè)元素的最大HBLT，其最右路徑的長度為O(logn)。合并操作僅需遍歷欲合并的HBLT的最右路徑。由于在兩條最右路徑的每個(gè)節(jié)點(diǎn)上只需耗時(shí)O(1)，因此將兩棵HBLT進(jìn)行合并具有對(duì)數(shù)復(fù)雜性。通過以上觀察，在合并算法中，僅需移動(dòng)右孩子。合并兩棵最大合并兩棵最大HBLTHBLT4040合并策略最好用遞歸來實(shí)現(xiàn)。令A(yù)、B為需要合并的兩棵最大HBLT，如果其中一個(gè)為空，則將另一個(gè)作為合并的結(jié)果，因此可以假設(shè)兩者均不為空。為實(shí)現(xiàn)合并，先比較兩個(gè)根元

13、素，較大者作為合并后的HBLT的根。假定A具有較大的根，且其左子樹為L，C是由A的右子樹與B合并而成的HBLT。A與B合并所得結(jié)果即是以A的根為根，L與C為左右子樹的最大HBLT。如果L的s值小于C的s值，則C為左子樹，否則L為左子樹。合并兩棵最大合并兩棵最大HBLTHBLT4141最大最大HBLTHBLT的合并的合并4242最大最大HBLTHBLT的合并的合并4343通過將n個(gè)元素插入到最初為空的最大HBLT中來對(duì)其進(jìn)行初始化，所需時(shí)間為O(nlogn)。更快的方法？初始化最大初始化最大HBLTHBLT4444為得到具有線性時(shí)間的初始化算法，首先創(chuàng)建n個(gè)最大HBLT，每個(gè)樹中僅包含n個(gè)元素中

14、的某一個(gè)，這n棵樹排成一個(gè)FIFO隊(duì)列，然后從隊(duì)列中依次刪除兩個(gè)HBLT，將其合并，然后再加入隊(duì)列末尾，直到最后只有一棵HBLT。初始化最大初始化最大HBLTHBLT4545構(gòu)造五個(gè)元素：7,1,9,11,2的一棵最大HBLT。首先構(gòu)造五個(gè)單元素的最大HBLT，并形成一個(gè)FIFO隊(duì)列。例例4646templatevoid MaxHBLT:Meld(HBLTNode* &x,HBLTNode* y)/合并兩棵根分別為*x和*y的左高樹，返回指向新根x的指針if(!y) return;if(!x) x=y; return; if(x-data data) S);Meld(x-RightCh

15、ild,y);if(!x-LeftChild) x-LeftChild=x-RightChild; x-RightChild=0; x-s=1;else if(x- LeftChild-s RightChild-s ) S LeftChild, x- RightChild); x-s= x- RightChild-s +1; 合并兩棵左高樹合并兩棵左高樹4747templateMaxHBLT& MaxHBLT:DeleteMax(T& x)/刪除最大元素，并將其放入xif(!root) throw OutOfBounds();x=root-data;/最大元素HBLTNode

16、*L=root-LeftChild;HBLTNode *R=root-RightChild;delete root;root=L;Meld(root,R);return *this;從最大從最大HBLTHBLT中刪除最大元素中刪除最大元素4848templatevoid MaxHBLT:Initialize(T a, int n)/初始化有n個(gè)元素的HBLT樹QueueHBLTNode * Q(n);Free(root);/刪除老節(jié)點(diǎn)/對(duì)樹的隊(duì)列進(jìn)行初始化for (int i=1;i=n;i+)HBLTNode *q=new HBLTNode (ai,1);Q.Add(q);HBLTNode

17、*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);最大最大HBLTHBLT的初始化的初始化4949n 堆排序(Heap Sort)n 機(jī)器調(diào)度(Machine Scheduling)n 霍夫曼編碼(Huffman Codes)應(yīng)用應(yīng)用5050先將要排序的n 個(gè)元素初始化為一個(gè)最大堆，然后每次從堆中提?。磩h除）元素。各元素將按遞減次序排列。初始化所需要的時(shí)間為(n)，每次刪除所需要的時(shí)間為O(logn) ，因此總時(shí)間為O(nlogn) 。堆排序堆排序5151temp

18、late void HeapSort(T a, int n)/ 利用堆排序算法對(duì)a1:n 進(jìn)行排序/ 創(chuàng)建一個(gè)最大堆MaxHeap H(1); H.Initialize(a,n,n) ;/ 從最大堆中逐個(gè)抽取元素T x;for (int i = n-1; i = 1; i-) H.DeleteMax(x) ;ai+1 = x;/ 在堆的析構(gòu)函數(shù)中保存數(shù)組aH.Deactivate(x) ;堆排序算法實(shí)現(xiàn)堆排序算法實(shí)現(xiàn)5252堆排序堆排序5353假設(shè)文本是由a,u,x,z組成的字符串，若這個(gè)字符串的長度為1000，每個(gè)字符用一個(gè)字節(jié)來存貯，共需1000個(gè)字節(jié)（即8000位）的空間。如果每個(gè)字符用

19、2位二進(jìn)制來編碼（00=a,01=x,10=u,11=z），則用2000位二進(jìn)制即可表示1000個(gè)字符。字符串a(chǎn)axuaxz的壓縮編碼為二進(jìn)制串11。例例- -壓縮壓縮5454此外，還需要一定的空間來存放編碼表，可采用如下格式來存儲(chǔ)：符號(hào)個(gè)數(shù),代碼1,符號(hào)1,代碼2,符號(hào)2,符號(hào)個(gè)數(shù)及每個(gè)符號(hào)分別用8位二進(jìn)制來表示，每個(gè)代碼需占用log2(符號(hào)個(gè)數(shù))位二進(jìn)制。因此，代碼表需占用5*8+4*2=48位，壓縮比為8000/2048=3.9。例例5555字符串a(chǎn)axuaxz的壓縮編碼為二進(jìn)制串111，每個(gè)字符的編碼具有相同的位數(shù)（兩位）。從左到右依次從位串中取出2位，通過查編碼表便可獲得原字符串。例

20、例- -解壓解壓5656一個(gè)字符出現(xiàn)的次數(shù)稱為頻率（frequency）在字符串a(chǎn)axuaxz中，a出現(xiàn)了三次。 a,x,u,z，在這個(gè)字符串中出現(xiàn)的頻率分別為3，2，1，1。頻率頻率5757采用可變長編碼。使用編碼(0=a,10=x,110=u,111=z) 。如果四個(gè)字符的出現(xiàn)頻率分別為(996,2,1,1)，則每個(gè)字符用2位編碼所得到編碼的長度為2000位，而用可變長編碼則僅為1006位。方案方案5858可變長編碼:沒有任何一個(gè)代碼是另一代碼的前綴。因此，當(dāng)從左到右檢查代碼時(shí)，可以很確定地得到與實(shí)際代碼相匹配的字符。解碼依據(jù)解碼依據(jù)5959可以利用擴(kuò)充二叉樹來派生一個(gè)實(shí)現(xiàn)可變長編碼的特殊類，該類滿足上述前綴性質(zhì)，被稱為霍夫曼編碼?；舴蚵幋a霍夫曼編碼6060在擴(kuò)充二叉樹中，可對(duì)從根到外部節(jié)點(diǎn)的路徑進(jìn)行編碼，方法是向左孩子移動(dòng)時(shí)取0，向右孩子移動(dòng)時(shí)取1?；舴蚵幋a霍夫曼編碼6161到節(jié)點(diǎn)(a,b,c,d,e,f)的路徑編碼分別為(00，010，011，100，101，11)霍夫曼編碼霍夫曼編碼6262對(duì)于一棵具有外部節(jié)點(diǎn)1， n 的擴(kuò)充二叉樹，對(duì)應(yīng)的壓縮編碼串的長度為：其中L