Python の優先キュー
優先キュー は抽象データ構造であり、キュー内の各データ/値には特定の優先順位があります。たとえば、航空会社では、ビジネスクラスまたはファーストクラスというタイトルが付いた手荷物は、他の手荷物よりも早く到着します。
Priority Queue は、次のプロパティを持つキューの拡張です。
- 優先度の高い要素は、優先度の低い要素よりも前にデキューされます。
- 2 つの要素の優先順位が同じ場合、それらはキュー内の順序に従って処理されます。
様々な アプリケーション コンピューター サイエンスの優先キューは次のとおりです。
ジョブ スケジューリング アルゴリズム、CPU およびディスク スケジューリング、さまざまなプロセス間で共有されるリソースの管理など。
優先キューとキューの主な違い:
- Queue では、最も古い要素が最初にデキューされます。一方、Priority Queue では、最も高い優先順位に基づいて要素がデキューされます。
- 要素が優先キューから取り出される場合、取得される結果は昇順または降順のいずれかでソートされます。一方、要素が単純なキューからポップされると、結果として FIFO 順序のデータが取得されます。
以下は、 簡単な実装 プライオリティキューの。
パイソン
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(> object> ):> > def> __init__(> self> ):> > self> .queue> => []> > def> __str__(> self> ):> > return> ' '> .join([> str> (i)> for> i> in> self> .queue])> > # for checking if the queue is empty> > def> isEmpty(> self> ):> > return> len> (> self> .queue)> => => 0> > # for inserting an element in the queue> > def> insert(> self> , data):> > self> .queue.append(data)> > # for popping an element based on Priority> > def> delete(> self> ):> > try> :> > max_val> => 0> > for> i> in> range> (> len> (> self> .queue)):> > if> self> .queue[i]>>> self> .queue[max_val]:> > max_val> => i> > item> => self> .queue[max_val]> > del> self> .queue[max_val]> > return> item> > except> IndexError:> > print> ()> > exit()> if> __name__> => => '__main__'> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())> |
出力：
12 1 14 7 14 12 7 1
上記のコードでは、削除の時間計算量は O(n) であることに注意してください。あ より良い実装 使うことです バイナリ ヒープ これは通常、優先キューを実装するために使用されます。 Python が提供するものに注意してください。 ヒープク 図書館にも。
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
