Wie kann ich die Prioritätswarteschlange implementieren, ohne integrierte Funktionen zu verwenden?

Question

das ist meine erste Frage hier überhaupt, also könnte Formatierung und solche ein wenig aus sein. Bitte hassen sie mich nicht :)

Also, was ich tue, eine Klasse macht genannt PQUEUE und was ich bereits:

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 

Ich versuche, eine Prioritätswarteschlange Klasse machen zu machen (wie Sie kann sehen) ohne heapq/queue-klassen oder die eingebauten listenmethoden zu verwenden.

Was ich nicht herausfinden kann ist, wie ich weitermachen würde. Ich habe versucht, überall online zu suchen, aber überall, wo ich aussehe, machen Leute das, indem sie entweder die eingebauten Listenmethoden importieren oder benutzen.

Hilfe sehr geschätzt! :)

Answer 1

Es hängt davon ab, was Ihre Definition von Priorität ist, aber Sie gehen zu müssen, über Ihre Sammlung selbst wiederholen, für den Ort suchen den nächsten Knoten einzufügen:

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 

Sie über muss natürlich eine priority zu Ihrer qNode hinzufügen, und Sie müssen möglicherweise genau einstellen, wo Sie einfügen werden, aber das sollte Sie den größten Teil des Weg dorthin bekommen.