優先隊列

**優先隊列:**另一種重要的緩存結構,

基于對一類二叉樹的認識,可以做出優先隊列的高效實作.

一.概念

作為緩存結構,優先隊列與棧和隊列類似,可以将資料元素儲存其中,可以通路和彈出,優先隊列的特點是存入其中的每項資料都另外附有一個數值,表示這個項的優先程度,稱為其優先級,優先隊列應該保證,在任何時候通路或者彈出的,總是當時在這個結構裡儲存的所有元素值中優先級最高的,如果該元素不彈出,再次通路還将得到它. 在一些場景中,可能出現不同元素具有相同優先級的情況,如果不止一個元素的優先級最高,優先隊列将保證通路或彈出的是它們中的一個,具體是哪個元素由内部實作确定.

抽象地看,需要緩存的是一個有序集S=(D,≤)的元素,這裡的"≤"是集合D上的一個全序(非嚴格的),表示元素的優先關系,優先隊列要求保證"最優先元素先出(先用)",具體集合和序由實際需要确定,統一集合上也可能有不同的序,在實作優先隊列時,必須确定使用的具體序關系.

允許D中不同元素具有相同優先級的情況,也就是說,可能有不同的a,b∈D,對它們a≤b且b≤a,這時就說a和b優先級相同,在這種應用場景中,如果要求保證優先級相同的元素先進先出(希望優先隊列同時具有隊列的FIFO性質),那就隻能趉效率較低的實作,如果隻要求保證通路(或彈出)的總是當時存在的最優先元素中的一個,不要求一定是其中最早進入優先隊列的元素,那麼就存在效率更高的實作.

優先隊列的操作

• 建立,判斷空(還可以有清空内容,确定目前元素個數等)
• 插入元素,通路和删除優先隊列裡(當時最優先)的元素

二. 基于線性表的實作

由于連續表可以存儲資料元素,顯然有可能作為優先隊列的實作基礎,資料項在連續表裡的存儲順序可用于表示資料之間的某種順序關系,對于優先隊列,這個順序可用于表示優先級關系,對于優先隊列,這個順序可用于表示優先級關系.例如,讓資料的存儲位置按優先順序排列.

按優先級順序存儲資料項是一種可能,但不必須,實際上存在着兩種可能的實作方案:

1. 在存入資料時,保證表中元素是在按優先順序排列(作為一種資料不變式), 任何時候都可以直接取到當時在表裡最優先的元素,采用有組織的元素存放方式,存入元素的操作比較麻煩,效率可能較低,但通路和彈出時比較友善
2. 存入資料時采用最簡單的方式(例如:對順序表存入表尾端,對連結表存入表頭), 需要取用時,通過檢索找到最優先的元素.采用這種無組織的方式存放元素,把選擇最優元素的工作推遲到通路/取出時,存入操作的效率高但是取用麻煩,如果需要多次通路同一個元素但不彈出,就應該采用其他技術,避免重複檢索.當然,也可以在一次檢索後記錄最優先元素,再次使用時就可以直接使用了,這種技術還需要與元素彈出互相配合.

下面采用在加入新資料的時候就設法确定正确的插入位置,保證表元素始終按優先順序排列,由于考慮采用采用連續表實作,為保證通路和彈出最優先資料項的操作能在O(1)時間内完成,最優先的項應該出現在表的尾端.

三. 基于list實作優先隊列

采用連續表技術,應該用一個list對象存儲資料,list對象能根據存儲元素的實際需要自動擴大存儲區,但也應該注意,任何時候都隻能在合法範圍内使用下标表達式,超範圍指派和取值是運作錯誤,會引發IndexError異常.是以,在需要插入新元素時,隻能先設法确定正确插入位置,而後調用list的insert(或其它操作)做定位插入.

# 需要存儲的元素用"≤"比較優先級,值較小的元素優先級更高

# 首先定義一個異常類,在優先隊列類裡使用
class PrioQueueError(ValueError):
    pass

# 将優先隊列定義一個類
class PrioQue:
    def __init__(self, elist=[])
    	self._elems = list(elist)
        self._elems.sort(reverse=True)
    
    # 插入操作需要找到正确的插入位置
    def enqueue(self, e):
        i = len(self._elems) - 1
        while i >= 0:
            if self._elems[i] <= e:
                i -= 1
            else:
                break
        self._elems.insert(i+1, e)
    
    def is_empty(self):
        return not self._elems
    
    def peek(self):
        if self.is_empty():
            raise PrioQueueError("in top")
        return self._elems[-1]
    
    def dequeue(self):
        if self.is_empty():
            raise PrioQueueError("in top")
        return self._elems.pop()
           

注意上面的參數預設值,以可變對象作為預設值是一種危險動作,應特别注意.在這裡用list轉換,有兩個作用:

• 首先對實參表(包括預設值空表)做一個拷貝,避免共享
• 使構造函數的實參可以是任何可疊代對象,例如疊代器或者元組等

對連續表實作的分析:

• 插入元素是O(n), 其他都是O(1). 即使插入時表的存儲區滿,需要換一塊存儲,操作效率的複雜度量級仍然是O(n)
• 另一種實作技術方案,插入元素是O(1), 檢查和彈出隊列中的最優先元素都是O(n)

無論采用怎樣的具體實作技術,在插入元素和取出元素的操作中總有一種是具有線性複雜度的操作