資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用Python的Queue和Heapdict模組實現優先佇列
優先佇列是一種抽象資料型別，類似於佇列或棧，其中每個元素都附加了一個優先順序。優先順序決定了元素從佇列中出隊的順序，優先順序高的元素優先於優先順序低的元素出隊。
優先佇列可以使用不同的資料結構來實現，例如堆、陣列或平衡樹。最常用的實現是堆，它是一種基於二叉樹的資料結構，每個節點的值都大於或等於其子節點的值。
優先佇列的型別
主要有兩種型別的優先佇列：最小優先佇列和最大優先佇列。在最小優先佇列中，優先順序最低的元素將首先出隊；在最大優先佇列中，優先順序最高的元素將首先出隊。優先佇列廣泛應用於任務排程、網路路由、作業優先順序和霍夫曼編碼等領域。
使用heapdict模組實現優先佇列
在Python中，我們有heapq、queue和heapdict模組。在本文中，我們將瞭解如何使用queue和heapdict模組來實現優先佇列。在heapdict模組中，我們有push和pop方法，用於根據優先順序將專案新增到佇列中，並從佇列中移除專案。
push方法將專案和優先順序作為輸入引數，並將專案新增到優先佇列和heapdict中。pop方法移除專案並返回被移除的專案，同時還在heapdict中移除該專案及其優先順序。
示例
在這個示例中，我們將建立一個名為PriorityQueueWithHeapdict的類，其中包含一個push函式，用於根據給定的優先順序將專案新增到佇列中。此函式將專案及其優先順序作為輸入引數。接下來，我們將使用定義的類和函式將專案新增到優先佇列中。
from queue import PriorityQueue
from heapdict import heapdict
class PriorityQueueWithHeapdict:
def __init__(self):
self._queue = PriorityQueue()
self._heapdict = heapdict()
def push(self, item, priority):
self._queue.put(priority)
self._heapdict[priority] = item
q = PriorityQueueWithHeapdict()
q.push('task 1', 3)
q.push('task 2', 1)
q.push('task 3', 2)
print("The items added to the priority queue and heapdict based on the priority")
輸出
The items added to the priority queue and heapdict based on the priority
示例
在前面的示例中，我們建立了包含push函式的類，現在我們將在這個類中建立pop函式。pop函式用於移除具有最高優先順序的專案，並在heapdict中移除該專案。
from queue import PriorityQueue
from heapdict import heapdict
class PriorityQueueWithHeapdict:
def __init__(self):
self._queue = PriorityQueue()
self._heapdict = heapdict()
def push(self, item, priority):
self._queue.put(priority)
self._heapdict[priority] = item
def pop(self):
priority = self._queue.get()
item = self._heapdict[priority]
del self._heapdict[priority]
return item
def is_empty(self):
return self._queue.empty()
q = PriorityQueueWithHeapdict()
q.push('task 1', 3)
q.push('task 2', 1)
q.push('task 3', 2)
while not q.is_empty():
print(q.pop())
輸出
task 2 task 3 task 1
更新於：2023年10月19日
266 次瀏覽
廣告