組み込み関数を使用せずに優先度キューを実装するにはどうすればよいですか？

Question

これはこれまでのところ私の最初の質問です。したがって、書式設定などが少し難しいかもしれません。私を嫌いしないでください:)

それでは、私がやっていることはPQUEUEというクラスを作っていると私は既に持っていることは次のとおりです。

class qNode: 
    def __init__(self,data=None, next=None): 
     self.data = data 
     self.next = next 
    def __str__(self): 
     return str(self.data) 

class PQUEUE: 

    def __init__(self): 
     self.head = None 
     self.foot = None 

    def push(self, value=None, priority=0): 
     #This is what I want to make 

    def pop(self): 
     x = self.front.data 
     self.front = self.front.next 
     return x 

    def clear(self): 
     self._head = None 
     self._foot = None 

私はあなたのように（プライオリティキュークラスを作成しようとしていますheapq/queueクラスやビルトインのリストメソッドを使用せずに参照できます）。

私が理解できないことは、これをどうやって進めるかです。私はどこでもオンラインで検索しようとしましたが、どこにいても、組み込みのリストメソッドをインポートしたり使用したりしている人が見ています。

非常に感謝します！ :)

Answer 1

次のノードを挿入する場所を探して、それは優先順位のあなたの定義は何であるかに依存しますが、あなたはあなたのコレクションの上に自分自身を反復処理する必要があるとしている：

node = self.head 
while node.next and node.next.priority > priority: 
    node = node.next 

if node.next is None: 
    node.next = qNode(value=value, next=None, priority=priority) 
    self.foot = node.next 
else: 
    new_node = qNode(value=value, next=node.next, priority=priority) 
    node.next = new_node 

あなた'LLもちろんqNodeにpriorityを追加する必要があります。挿入する場所を正確に調整しなければならない場合がありますが、ほとんどの場合、この方法で調整する必要があります。