文章目錄

一、優先級佇列簡介
- 1. 簡介
- 2. 定義
- 3. ADT
二、優先級佇列實作
- 1. 佇列記錄的鍵值對保存
- 2. 定義優先級佇列的基類
- 3. 使用未排序位置串列實作
- - `__init__()`
  - `_find_min()`
  - `__len__()`
  - `add()`
  - `min()`
  - `remove_min()`
- 4. 使用排序位置串列實作
- - `__init__()`
  - `__len__()`
  - `add()`
  - `min()`
  - `remove_min()`
- 5. 比較兩種基于位置串列的實作
三、附錄：完整代碼測驗

一、優先級佇列簡介

1. 簡介

在文章【資料結構Python描述】佇列和雙端佇列簡介及其高效率版本Python實作中，我們引入并實作了佇列這種資料結構，對其進行元素的增刪遵循先進先出的原則，并以現實中排隊享受服務作為類比，

然而，上述普通佇列的模型并不能完全滿足實際的需求，例如：你僅是某銀行的普通等級客戶，當你去銀行取號辦理業務時，可能雖然后面的人來得比你晚，但是由于他可能是該行的白金等級客戶，那么很有可能他會在你之前被叫號，

因此，對于上述情況，取號的早晚并不會被當作判斷下一個被叫號的唯一標準，更重要是看客戶的等級，本文就將介紹并實作用以描述這類場景的資料結構——優先級佇列，實際上，在上述案例中，客戶等級就是優先級，

2. 定義

優先級佇列：優先級佇列是指這樣一種抽象資料型別，即其中包含一系列具有不同優先級的元素，除了像普通佇列可以在隊尾插入元素外，優先級佇列可以在任意位置插入元素，最重要的是在每次從優先級佇列中移除的元素都具有最高的優先級，

對于優先級佇列，在向其中插入一個元素時，用戶就會同時以鍵的形式為其指定一個優先級，而鍵值最小的元素會在下一次元素出隊操作時被從優先級佇列中移除，例如：如果元素鍵值為1的優先級要高于元素鍵值為2的元素，

需要注意的是，盡管通常元素的優先級即鍵都用整數來表示，但原則上任意兩個通過同一個類實體化后得到的Python物件a、b，只要對于a < b運算有一致的含義，則這些物件都可以作為代表元素優先級的鍵，

3. ADT

為了后續實作優先級佇列，這里將一個元素和其優先級表示為一個鍵值對的形式，而且在本文實作的優先級佇列ADT包含以下幾個方法：

p.add(k, v)：將鍵k和表示元素的值v作為一個記錄插入優先級佇列p中；
p.min()：回傳一個元組(k, v)，k和v分別代表優先級佇列p中一條記錄的鍵和值；
p.remove_min()：將優先級佇列p中鍵值k最小的記錄洗掉并回傳一個元組(k, v)，如果此時p為空則拋出例外；
p.is_empty()：如果優先級佇列p不包含任何記錄則回傳True；
__len__()：回傳優先級佇列p中記錄條目數，

需要注意的是，一個優先級佇列中的多條記錄可能會有相同的鍵，在這種情況下min()和remove_min()兩個方法將會隨機回傳有最小鍵那條記錄的元素，

下面是使用上述ADT中的方法對一個優先級佇列進行一系列操作后預期的結果：

操作	回傳值	優先級佇列
`p.add(5, A)`	`None`	`{(5, A)}`
`p.add(9, C)`	`None`	`{(5, A), (9, C)}`
`p.add(3, B)`	`None`	`{(3, B), (5, A), (9, C)}`
`p.add(7, D)`	`None`	`{(3, B), (5, A), (7, D), (9, C)}`
`p.min()`	`(3, B)`	`{(3, B), (5, A), (7, D), (9, C)}`
`p.remove_min()`	`(3, B)`	`{(5, A), (7, D), (9, C)}`
`p.remove_min()`	`(5, A)`	`{(7, D), (9, C)}`
`len(p)`	2	`{(7, D), (9, C)}`
`p.remove_min()`	`(7, D)`	`{(9, C)}`
`p.remove_min()`	`(9, C)`	`{}`
`p.is_empty()`	`True`	`{}`

二、優先級佇列實作

本節將使用【資料結構Python描述】位置串列簡介與Python版手工實作中的位置串列存盤優先級佇列中以鍵值對形式存盤的每條記錄，并且，基于佇列中的記錄是否按照鍵排序，下面提供兩種實作方式，

1. 佇列記錄的鍵值對保存

對于優先級佇列的實作，首先需要考慮的是如何保存優先級佇列一條記錄中的鍵k和值v，實際上，早在之前實作單鏈表時，我們就遇到過類似情況，即單鏈表的每一個結點也需要參考兩個物件，即：業務物件元素和下一個結點，

這里考慮仿照單鏈表實作中定義的結點類_Node定義一個_Item類，其實體屬性key參考一條記錄的鍵，實體屬性value參考同一條記錄的值，不同的是，在優先級佇列的實作類中嵌套定義類_Item，

2. 定義優先級佇列的基類

實際上，由于后續我們將根據優先級佇列中的記錄是否按照鍵的大小進行排序提供兩種不同實作，因此為提高代碼復用程度并建立不同實作之間的聯系，下面仿照樹的實作先定義一個包含兩種實作共有方法的抽象基類PriorityQueueBase：

from abc import ABCMeta, abstractmethod


class PriorityQueueBase(metaclass=ABCMeta):
    """優先級佇列的基類"""

    class _Item:
        """用于表示優先級佇列中以鍵值對形式保存的記錄條目類"""

        def __init__(self, k, v):
            self.key = k
            self.value = v

        def __lt__(self, other):
            """
            多載運算子<，使得可按照兩個_Item實體物件的屬性key來比較這兩個實體物件
            :param other: _Item的另一個實體物件
            :return: Boolean
            """
            return self.key < other.key

    @abstractmethod
    def __len__(self):
        """
        具體子類中需實作的抽象方法，用于具體子類的實體物件支持len(obj)語法
        :return: 物件記錄條目數
        """
    
    @abstractmethod
    def add(self, key, value):
        """
        具體子類中需實作的抽象方法，用于向優先級佇列中插入一條包含鍵和值的記錄
        :param key: 鍵
        :param value: 值
        :return: None
        """
        
    @abstractmethod
    def min(self):
        """
        具體子類中需實作的抽象方法，用于回傳（但不洗掉）優先級佇列中鍵最小的記錄
        :return: 優先級佇列中鍵最小的記錄
        """
        
    @abstractmethod
    def remove_min(self):
        """
        具體子類中需實作的抽象方法，用于回傳并洗掉優先級佇列中鍵最小的記錄
        :return: 優先級佇列中鍵最小的記錄
        """

    def is_empty(self):
        """判斷優先級佇列是否為空"""
        return len(self) == 0

需要注意的是：

關于抽象基類的定義方式可見Python中的繼承、抽象基類和介面；
關于使用抽象基類的意義，可見【資料結構Python描述】樹的簡介、基本概念和手動實作一個二叉樹（真·全網最全！）

3. 使用未排序位置串列實作

下面給出繼承抽象基類PriorityQueueBase實作的第一個優先級佇列UnsortedPriorityQueue，其中的所有鍵值對記錄均保存在【資料結構Python描述】位置串列簡介與Python版手工實作中實作的位置串列PositionalList中，且每次向佇列中添加一條記錄時直接向隊尾添加，

`init()`

首先，對于初始化方法，由于優先級佇列的使用者無需關心底層實作，因此這里將用于存盤優先級佇列記錄的實體屬性_data定義為非公有的且參考一個位置串列的實體物件：

def __init__(self):
    """創建一個空的優先級佇列，其記錄底層由位置串列保存"""
    self._data = PositionalList()

`_find_min()`

由于min()和remove_min()兩個方法均需要先找到佇列中鍵最小的那條記錄，因此為提高代碼復用程度，這里定義這樣一個非公有方法，該方法回傳佇列中鍵最小記錄所在位置：

def _find_min(self):
    """查找并回傳優先級佇列中鍵最小的記錄，并回傳其在位置串列中的位置"""
    if self.is_empty():
        raise Empty('當前優先級佇列為空！')
    small = self._data.first()
    walk = self._data.after(small)
    while walk is not None:
        if walk.element() < small.element():
            small = walk
        walk = self._data.after(walk)
    return small

`len()`

該方法只需直接回傳呼層位置串列容器的元素個數：

def __len__(self):
    """支持實體物件使用len(obj)語法回傳obj長度的方法"""
    return len(self._data)

`add()`

該方法只需：

先將鍵值對key-value封裝為_Item的一個實體；
然后呼叫add_last()方法將該條記錄插入位置串列中即可：

def add(self, key, value):
    """將鍵值對key-value封裝為一條記錄插入位置串列最后位置"""
    self._data.add_last(self._Item(key, value))

`min()`

該方法只需：

先呼叫實用方法_find_min()得到鍵最小記錄的位置；
得到并回傳該位置處記錄中的鍵和值：

def min(self):
    """回傳（但不洗掉）優先級佇列中鍵最小的記錄"""
    p = self._find_min()
    item = p.element()
    return item.key, item.value

`remove_min()`

實作類似min()，只是在回傳鍵最小記錄的鍵和值之前要洗掉該條記錄：

def remove_min(self):
    """回傳并洗掉優先級佇列中鍵最小的記錄"""
    p = self._find_min()
    item = self._data.delete(p)
    return item.key, item.value

4. 使用排序位置串列實作

下面給出繼承抽象基類PriorityQueueBase實作的第二個優先級佇列SortedPriorityQueue，其中的所有鍵值對記錄也均保存在【資料結構Python描述】位置串列簡介與Python版手工實作中實作的位置串列PositionalList中，但與上述實作每次向佇列中添加一條記錄時都直接向隊尾添加不同的是，下面的實作中每次添加記錄的操作完成后都確保該記錄插入后佇列中記錄按鍵的大小升序排列，

`init()`

實作同上述UnsortedPriorityQueue中的同名方法：

def __init__(self):
    """創建一個空的優先級佇列，其所有記錄在底層由位置串列保存"""
    self._data = PositionalList()

`len()`

實作同上述UnsortedPriorityQueue中的同名方法：

def __len__(self):
    """支持優先級佇列實體物件使用len(obj)語法回傳obj長度的方法"""
    return len(self._data)

`add()`

同上述UnsortedPriorityQueue中的同名方法實作不同的是，這里在向優先級佇列插入一條鍵值對形式的記錄后都保證所有記錄是按照鍵大小從左到右升序排列：

def add(self, key, value):
    """將鍵值對key-value封裝為一條記錄插入位置串列，保證該記錄插入后佇列中記錄按鍵的大小升序排列"""
    item = self._Item(key, value)  # 根據鍵值對key-value創建一條記錄
    walk = self._data.last()  # 將輔助指標初始化為參考當前佇列最后一條記錄
    while walk is not None and item < walk.element():  # 遍歷佇列，保證該記錄插入后佇列中記錄按鍵的大小升序排列
        walk = self._data.before(walk)
    if walk is None:  # 如果新記錄的鍵小于當前佇列所有鍵，則在佇列頭部插入記錄
        self._data.add_first(item)
    else:  # 否則在輔助指標參考的記錄后插入記錄
        self._data.add_after(walk, item)

`min()`

實作類似上述UnsortedPriorityQueue中的同名方法：

def min(self):
    """回傳（但不洗掉）優先級佇列中鍵最小的記錄"""
    if self.is_empty():
        raise Empty('當前優先級佇列為空！')
    p = self._data.first()
    item = p.element()
    return item.key, item.value

`remove_min()`

實作類似上述UnsortedPriorityQueue中的同名方法：

def remove_min(self):
    """回傳并洗掉優先級佇列中鍵最小的記錄"""
    if self.is_empty():
        raise Empty('當前優先級佇列為空！')
    item = self._data.delete(self._data.first())
    return item.key, item.value

5. 比較兩種基于位置串列的實作

對于上述兩種不同的優先級佇列實作，其ADT方法的時間復雜度對比如下表所示：

方法	`UnsortedPriorityQueue`	`SortedPriorityQueue`
`__len__`	O ( 1 ) O(1) O(1)	O ( 1 ) O(1) O(1)
`is_empty`	O ( 1 ) O(1) O(1)	O ( 1 ) O(1) O(1)
`add`	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)
`min`	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)
`remove_min`	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)

上述時間復雜度分析成立的前提是：用于存盤優先級佇列記錄的位置串列底層使用雙向鏈表實作，

三、附錄：完整代碼測驗

下面是對上述實作的UnsortedPriorityQueue和SortedPriorityQueue中的ADT方法進行測驗的完整代碼：

from abc import ABCMeta, abstractmethod
from positional_list import PositionalList


class Empty(Exception):
    """嘗試對空優先級佇列進行洗掉操作時拋出的例外"""
    pass


class PriorityQueueBase(metaclass=ABCMeta):
    """優先級佇列的基類"""

    class _Item:
        """用于表示優先級佇列中一條記錄的類"""

        def __init__(self, k, v):
            self.key = k
            self.value = v

        def __lt__(self, other):
            """
            多載運算子<，使得可按照兩個_Item實體物件的屬性key來比較這兩個實體物件
            :param other: _Item的另一個實體物件
            :return: Boolean
            """
            return self.key < other.key

    @abstractmethod
    def __iter__(self):
        """具體子類中需實作的抽象方法，用于生成優先級佇列中所有記錄的一個迭代"""

    @abstractmethod
    def __len__(self):
        """
        具體子類中需實作的抽象方法，用于具體子類的實體物件支持len(obj)語法
        :return: 物件記錄條目數
        """

    @abstractmethod
    def add(self, key, value):
        """
        具體子類中需實作的抽象方法，用于向優先級佇列中插入一條包含鍵和值的記錄
        :param key: 鍵
        :param value: 值
        :return: None
        """

    @abstractmethod
    def min(self):
        """
        具體子類中需實作的抽象方法，用于回傳（但不洗掉）優先級佇列中鍵最小的記錄
        :return: 優先級佇列中鍵最小的記錄
        """

    @abstractmethod
    def remove_min(self):
        """
        具體子類中需實作的抽象方法，用于回傳并洗掉優先級佇列中鍵最小的記錄
        :return: 優先級佇列中鍵最小的記錄
        """

    def __str__(self):
        """
        回傳物件的字串表示形式，使得可以使用print(obj)語法列印物件obj得到直觀的字串
        :return: 物件的字串表示形式
        """
        return str(list(self))

    def is_empty(self):
        """判斷優先級佇列是否為空"""
        return len(self) == 0


class UnsortedPriorityQueue(PriorityQueueBase):
    """記錄不按鍵的大小排序的優先級佇列具體實作類"""

    def __init__(self):
        """創建一個空的優先級佇列，其所有記錄在底層由位置串列保存"""
        self._data = PositionalList()

    def __iter__(self):
        """生成優先級佇列中所有記錄的一個迭代"""
        cursor = self._data.first()
        while cursor is not None:
            item = cursor.element()
            yield item.key, item.value
            cursor = self._data.after(cursor)

    def _find_min(self):
        """查找并回傳優先級佇列中鍵最小的記錄，并回傳其在位置串列中的位置"""
        if self.is_empty():
            raise Empty('當前優先級佇列為空！')
        small = self._data.first()
        walk = self._data.after(small)
        while walk is not None:
            if walk.element() < small.element():
                small = walk
            walk = self._data.after(walk)
        return small

    def __len__(self):
        """支持優先級佇列實體物件使用len(obj)語法回傳obj長度的方法"""
        return len(self._data)

    def add(self, key, value):
        """將鍵值對key-value封裝為一條記錄插入位置串列最后位置"""
        self._data.add_last(self._Item(key, value))

    def min(self):
        """回傳（但不洗掉）優先級佇列中鍵最小的記錄"""
        p = self._find_min()
        item = p.element()
        return item.key, item.value

    def remove_min(self):
        """回傳并洗掉優先級佇列中鍵最小的記錄"""
        p = self._find_min()
        item = self._data.delete(p)
        return item.key, item.value


class SortedPriorityQueue(PriorityQueueBase):
    """記錄按照鍵的大小排序的優先級佇列具體實作類"""

    def __init__(self):
        """創建一個空的優先級佇列，其所有記錄在底層由位置串列保存"""
        self._data = PositionalList()

    def __iter__(self):
        """生成優先級佇列中所有記錄的一個迭代"""
        cursor = self._data.first()
        while cursor is not None:
            item = cursor.element()
            yield item.key, item.value
            cursor = self._data.after(cursor)

    def __len__(self):
        """支持優先級佇列實體物件使用len(obj)語法回傳obj長度的方法"""
        return len(self._data)

    def add(self, key, value):
        """將鍵值對key-value封裝為一條記錄插入位置串列，保證該記錄插入后佇列中記錄按鍵的大小升序排列"""
        item = self._Item(key, value)  # 根據鍵值對key-value創建一條記錄
        walk = self._data.last()  # 將輔助指標初始化為參考當前佇列最后一條記錄
        while walk is not None and item < walk.element():  # 遍歷佇列，保證該記錄插入后佇列中記錄按鍵的大小升序排列
            walk = self._data.before(walk)
        if walk is None:  # 如果新記錄的鍵小于當前佇列所有鍵，則在佇列頭部插入記錄
            self._data.add_first(item)
        else:  # 否則在輔助指標參考的記錄后插入記錄
            self._data.add_after(walk, item)

    def min(self):
        """回傳（但不洗掉）優先級佇列中鍵最小的記錄"""
        if self.is_empty():
            raise Empty('當前優先級佇列為空！')
        p = self._data.first()
        item = p.element()
        return item.key, item.value

    def remove_min(self):
        """回傳并洗掉優先級佇列中鍵最小的記錄"""
        if self.is_empty():
            raise Empty('當前優先級佇列為空！')
        item = self._data.delete(self._data.first())
        return item.key, item.value


if __name__ == '__main__':

    # 測驗UnsortedPriorityQueue
    u_q = UnsortedPriorityQueue()
    u_q.add(5, 'A')
    print(u_q)  # [(5, 'A')]

    u_q.add(9, 'C')
    print(u_q)  # [(5, 'A'), (9, 'C')]

    u_q.add(3, 'B')
    print(u_q)  # [(5, 'A'), (9, 'C'), (3, 'B')]

    u_q.add(7, 'D')
    print(u_q)  # [(5, 'A'), (9, 'C'), (3, 'B'), (7, 'D')]

    print(u_q.min())  # (3, 'B')
    print(u_q.remove_min())  # (3, 'B')
    print(u_q)  # [(5, 'A'), (9, 'C'), (7, 'D')]
    print(len(u_q))  # 3
    print(u_q.is_empty())  # False

    # 測驗SortedPriorityQueue
    s_q = SortedPriorityQueue()
    s_q.add(5, 'A')
    print(s_q)  # [(5, 'A')]

    s_q.add(9, 'C')
    print(s_q)  # [(5, 'A'), (9, 'C')]

    s_q.add(3, 'B')
    print(s_q)  # [(3, 'B'), (5, 'A'), (9, 'C')]

    s_q.add(7, 'D')
    print(s_q)  # [(3, 'B'), (5, 'A'), (7, 'D'), (9, 'C')]

    print(s_q.min())  # (3, 'B')
    print(s_q.remove_min())  # (3, 'B')
    print(s_q)  # [(5, 'A'), (7, 'D'), (9, 'C')]
    print(len(s_q))  # 3
    print(s_q.is_empty())  # False

轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/142220.html

標籤：區塊鏈

上一篇：商業資料分析從入門到入職（8）Python模塊、檔案IO和面向物件

下一篇：Python背景關系管理器

【資料結構Python描述】優先級佇列簡介及Python手工實作

文章目錄

一、優先級佇列簡介

1. 簡介

2. 定義

3. ADT

二、優先級佇列實作

1. 佇列記錄的鍵值對保存

2. 定義優先級佇列的基類

3. 使用未排序位置串列實作

__init__()

_find_min()

__len__()

add()

min()

remove_min()

4. 使用排序位置串列實作

__init__()

__len__()

add()

min()

remove_min()

5. 比較兩種基于位置串列的實作

三、附錄：完整代碼測驗

`init()`

`_find_min()`

`len()`

`add()`

`min()`

`remove_min()`

`init()`

`len()`

`add()`

`min()`

`remove_min()`