《數(shù)據(jù)結(jié)構(gòu)》6優(yōu)先隊(duì)列

優(yōu)先隊(duì)列（堆）priorityqueue應(yīng)用于操作系統(tǒng)的進(jìn)程調(diào)度策略中優(yōu)先隊(duì)列的基本模型優(yōu)先隊(duì)列的實(shí)現(xiàn)思考二叉堆優(yōu)先隊(duì)列的應(yīng)用小結(jié)優(yōu)先隊(duì)列（堆）優(yōu)先隊(duì)列的基本模型優(yōu)先隊(duì)列插入刪除最小者至少允許兩種操作：insertdeleteMin等價(jià)于enqueue(入隊(duì))是dequeue(出隊(duì))在優(yōu)先隊(duì)列中的等價(jià)操作優(yōu)先隊(duì)列實(shí)現(xiàn)思考鏈表：在表頭執(zhí)行插入操作O(1)，遍歷該鏈表實(shí)現(xiàn)刪除最小元素O(n)。二叉查找樹：deleteMin操作會(huì)損害樹的平衡，使得右子樹加重。另外，二叉平衡樹支持更多的但在優(yōu)先隊(duì)列中不需要的操作。二叉堆二叉堆(binaryheap)堆的定義二叉堆的性質(zhì)：結(jié)構(gòu)性質(zhì)、堆序性質(zhì)二叉堆的操作：insert、deleteMin、buildHeap二叉堆的應(yīng)用：選擇問題、事件模擬堆的定義堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或(小頂堆)(大頂堆)若將此序列所存儲(chǔ)的一維數(shù)組R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。堆的定義小頂堆：

根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小頂堆。大頂堆：

根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大頂堆。注意：

①堆中任一子樹亦是堆。

②以上討論的堆實(shí)際上是二叉堆(BinaryHeap)，類似地可定義k叉堆。堆的定義（13，38，27，50，76，65，49，97）1338275076654997（96，83，27，38，11，9）小頂堆96832738119大頂堆二叉堆的結(jié)構(gòu)性質(zhì)二叉堆是一棵完全二叉樹。所以，可以用數(shù)組來表示。ABCDEFGHIJABCDEFGHIJ012345678910111213

對(duì)于數(shù)組中任一位置i上的元素，其左孩子在位置2i上，右孩子在左孩子后的位置(2i+1)上。它的父節(jié)點(diǎn)在i/2的位置上。圖中二叉堆大小的限界是13個(gè)元素。在一個(gè)二叉堆中，對(duì)于每一個(gè)節(jié)點(diǎn)X，X的父親中的關(guān)鍵字小于（或等于）X中的關(guān)鍵字，根節(jié)點(diǎn)除外。二叉堆的堆序性質(zhì)132116631196865263213211624311968652632二叉堆非二叉堆根據(jù)二叉堆的堆序性質(zhì)最小元總可以在根處找到所有的操作都要保證堆序性質(zhì)。二叉堆的操作—insert插入操作的基本思想：創(chuàng)建一個(gè)空穴，再將空穴上冒，這種策略叫上濾(percolateup)。二叉堆的操作—insert13211624311968652632

嘗試插入1413211624311968652632312114publicvoidinsert(AnyTypex){if(currentSize==array.length-1)enlargeArray(array.length*2+1);inthole=++currentSize;for(;hole>1&&pareTo(array[hole/2])<0;hole/=2)array[hole]=array[hole/2];array[hole]=x;}二叉堆的操作—insert二叉堆的操作—deleteMindeleteMin(刪除最小元)操作的基本思想：即刪除根節(jié)點(diǎn)。在根節(jié)點(diǎn)建立一個(gè)空穴，然后將堆中最后一個(gè)元素X移動(dòng)到該堆的某個(gè)地方后仍構(gòu)成二叉堆這種策略叫下濾(percolatedown)或篩選二叉堆的操作—deleteMin13211619196865263231211413211619196865263231211414192631publicAnyTypedeleteMin(){if(isEmpty())thrownewUnderflowException();AnyTypeminItem=findMin();array[1]=array[currentSize--];percolateDown(1);returnminItem;}二叉堆的操作—deleteMinprivatevoidpercolateDown(inthole){intchild;AnyTypetmp=array[hole];for(;hole*2<=currentSize;hole=child){child=hole*2;

if(child!=currentSize&&array[child+1].compareTo(array[child])<0)child++;if(array[child].compareTo(tmp)<0)array[hole]=array[child];

elsebreak;}array[hole]=tmp;}二叉堆的操作—deleteMin二叉堆的操作—buildHeap構(gòu)建堆buildHeap的基本思想：從無序序列的第n/2個(gè)元素（即此無序序列對(duì)應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)下濾(篩選)。將含8個(gè)元素的無序序列(59，97，56，50，53，65，62，76)調(diào)整成小頂堆。59975650536562761.先將無序序列建立完全二叉樹二叉堆的操作—buildHeap堆排序—建立堆過程59975650536562762.按照建堆思想，將(59，97，56，50，53，65，62，76)調(diào)整成小頂堆。5076975950975953publicBinaryHeap(AnyType[]items){currentSize=items.length;array=(AnyType[])newComparable[(currentSize+2)*11/10];inti=1;for(AnyTypeitem:items)array[i++]=item;

buildHeap();}二叉堆的操作—buildHeap二叉堆的操作—buildHeapprivatevoidbuildHeap(){for(inti=currentSize/2;i>0;i--)

percolateDown(i);}優(yōu)先隊(duì)列的應(yīng)用—選擇問題輸入N個(gè)元素及