優(yōu)先隊(duì)列及其應(yīng)用ppt課件(存儲版)
【正文】 隊(duì)列的順序由元素的優(yōu)先級決定，如： ? 醫(yī)院中的急診處理； ? 操作系統(tǒng)中使用優(yōu)先隊(duì)列進(jìn)行作業(yè)調(diào)度； ? 事件驅(qū)動模擬處理。 ? 當(dāng)機(jī)器可用，選擇優(yōu)先級最大的任務(wù)執(zhí)行，任務(wù)隊(duì)列操作： 1) 新任務(wù)到達(dá)，插入最大優(yōu)先隊(duì)列 2) 一旦機(jī)器可以開始運(yùn)行一個(gè)新任務(wù)，將具有最大優(yōu)先權(quán)的任務(wù)從該機(jī)器的隊(duì)列中刪除，并開始執(zhí)行它。 設(shè)有 n個(gè)數(shù)據(jù)元素的值為（ k1,k2,…, kn），如果它們滿足以下的關(guān)系： ki≤k2i且 ki≤k2i+1（或 ki≥k2i且 ki≥k2i+1）（ i=1,…, n/2），則稱之為堆（ Heap）。 k:=i。{把第 k個(gè)結(jié)點(diǎn)往下調(diào) } begin while k+k=n do begin i:=min{ 2k,2k+1}。 up(n) end。如下圖： ① 7,1合并成為 a) ② 9,11合并成為 b) ③ 2和 a)合并成為 c) ④ 最后 b)和 c)合并成為 d) 復(fù)雜性分析 ? 初始化的復(fù)雜性 – n是 2的冪：合并 n/2對一個(gè)元素的 HBLT?合并n/4對二個(gè)元素的 HBLT... –合并兩棵 2i個(gè)元素的 HBLT： O(i+1) –總時(shí)間復(fù)雜性 )()2()8*34*22( nOinOnnnO i ????? ??斜堆（ skew heap） ? 斜堆可遞歸的定義如下： ● 只有一個(gè)元素的堆是斜堆。 ? 合并方法是： ? 如果倒數(shù)第二棵樹有左子樹，那么把左子樹變?yōu)橛易訕洹＿@時(shí)候我們可以采用貪心方法，盡量選截止時(shí)間比較晚，同時(shí)需要時(shí)間比較少的任務(wù)完成是最好的。如果 CkCi+1那么根據(jù)定理 1，將 K,i+1替換后肯定更優(yōu)。顯然，使用大根堆即能滿足題目要求。輸入格式是這樣的： ? 試題有若干組數(shù)據(jù)。 ? 隨著 i的增加，會有一些決策從第一類轉(zhuǎn)到第二類。 數(shù)據(jù)： 2 1 9 3 2 分析 (1) ? 設(shè) f(i)表示要將前 i個(gè)數(shù)改得合法需要的最少步數(shù)。 ? 從外到內(nèi)初步處理，用小根堆存儲讀入的數(shù)據(jù)，每做一次初步累加結(jié)果即可。 。如果第 i+1個(gè)任務(wù)直接加入后，依然滿足題目要求，那么前 i+1個(gè)任務(wù)最后方案集合就是 Ui+1=Ui+{i+1}。現(xiàn)在你一個(gè)人希望從 0時(shí)刻開始完成盡量多的任務(wù)。 ? 對集合中的樹，按照根節(jié)點(diǎn)的值從小到大排序。 3) 通過最右路徑（即，此路徑是從 x開始沿右孩子移動）從 x到達(dá)外部節(jié)點(diǎn)的路徑長度為 s(x) 證明 由 s(x) 定義 ?從 x向下的 s(x)1層內(nèi)沒有外部節(jié)點(diǎn)（否則 s(x) 將更小） 子樹第一層只有 x，下一層有兩個(gè)， ...， 第 s (x)1層有個(gè) 2s (x) 1，節(jié)點(diǎn)數(shù)目至少為 由 1) 可得 2） 根據(jù) s 的定義，及 HBLT一個(gè)節(jié)點(diǎn)的左孩子的 s 值總是大于等于其右孩子的 s 值，可以推得 3）成立。 {添加一個(gè)值為 x的元素 } begin inc(n)。接著把位置 w上的新元素不斷下調(diào)，直到滿足堆的性質(zhì)。 ? {把第 k個(gè)結(jié)點(diǎn)上調(diào) } ? begin ? while k1 do ? begin ? i:=k div 2。 輸入輸出 輸入 每行一次操作，有如下三種： 1 x：表示插入 X這個(gè)數(shù) 2 ：表示詢問當(dāng)前最小值 3： 表示刪除最小值 輸出 對于每個(gè)詢問最小值操作，輸出一行，每行僅一個(gè)數(shù)，表示當(dāng)前的最小值。 ? 如果每個(gè)用戶所需時(shí)間相同，但用戶愿意支付的費(fèi)用不同，則可以用支付費(fèi)用作為優(yōu)先權(quán)，一旦機(jī)器可用，所交費(fèi)用最多的用戶可最先得到服務(wù)，這時(shí)就要選擇最大優(yōu)先隊(duì)列。 ? 優(yōu)先隊(duì)列的基本操作 ADT MaxPriorityQueue { 實(shí)例 有限的元素集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)操作 Create( )：創(chuàng)建一個(gè)空的優(yōu)先隊(duì)列 Size( )：返回隊(duì)列中的元素?cái)?shù)目 Max( )：返回具有最大優(yōu)先權(quán)的元素 Insert(x)：將 x插入隊(duì)列 DeleteMax(x)：從隊(duì)列中給刪除具有最大優(yōu)先權(quán)的元素，并將該元素返回至 x } ? 假設(shè)我們對機(jī)器服務(wù)進(jìn)行收費(fèi)。 ? 優(yōu)先隊(duì)列的線性表實(shí)現(xiàn) ? 優(yōu)先隊(duì)列的另一種實(shí)現(xiàn)方式 —— 堆（ Heap）。 堆（ Heap） 9 17 23 78 87 65 31 53 45 87 78 45 9 31 53 23 17 65 最小堆（ MinHeap） 最大堆（ MaxHeap） 9 17 65 23 45 78 87 53 31 87 78 53 45 65 9 31 17 23 ? 最?。ù螅┒?：位于 堆頂 （即完全二叉樹的根節(jié)點(diǎn)位置）的節(jié)點(diǎn)的值是整個(gè)序列中最?。ù螅┑?。 {交換結(jié)點(diǎn) i和 k} ? end ? else exit。 {如果 2k+1不存在直接返回 k+k否則返回 2個(gè)中間的值較小的元素 } if st[i]st[k] then begin swap(i,k)。 PROC del(x:longint)。 ● 兩個(gè)斜堆通過斜堆的合并操作，得到的結(jié)果
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1