Python - Hash-Heap-Implementierung

Question

Ich habe ein Stream-Daten kommen, und ich bin Beibehaltung von ihnen eins nach dem anderen in einen Haufen (Prioritätswarteschlange) drückt, sieht die resultierende Haufen wie:

[(a,1), (b,2), (c, 7), (d, 2), ...] 

Weil ich brauche um die Elemente zu aktualisieren (z. B. (a, 1) zu ändern (a, 2) oder zu löschen (c, 7)), um die Zeit kontinuierlich zu durchlaufen. Um Elemente in einem Heap effizient zu finden und zu entfernen, möchte ich eine Hash-Tabelle mit dem Speicherort aller Elemente in dem Heap erstellen, die in der Hash-Tabelle gespeichert sind.

Damit jedes Mal, wenn ich ein Element aktualisieren möchte, kann ich die Hashtabelle verwenden, um es zu finden und Änderungen leicht in den Heap zu ändern, simultan die Position jedes Elements in der Hashtabelle aktualisieren. How to implement O(1) deletion on min-heap with hashtable mit C++ Code wie folgt: wenn jemand mich auf die Idee erklären kann, fragen

template<typename state, typename CmpKey, class dataStructure> 
bool AStarOpenClosed<state, CmpKey, dataStructure>::HeapifyUp(unsigned int index) 
{ 
     if (index == 0) return false; 
     int parent = (index-1)/2; 
     CmpKey compare; 

     if (compare(elements[theHeap[parent]], elements[theHeap[index]])) 
     { 
       // Perform normal heap operations 
       unsigned int tmp = theHeap[parent]; 
       theHeap[parent] = theHeap[index]; 
       theHeap[index] = tmp; 
       // Update the element location in the hash table 
       elements[theHeap[parent]].openLocation = parent; 
       elements[theHeap[index]].openLocation = index; 
       HeapifyUp(parent); 
       return true; 
     } 
     return false; 
} 

Ich habe wenig Erfahrung mit C++, Hilfe oder eine Python-Version Code liefern

Die gleiche Frage wurde in diesem Beitrag nicht gefragt von einer solchen Implementierung?

Answer 1

Mein Verständnis ist, dass das erste Element in Ihrem Paar dient als Schlüssel und das zweite Element als Datennutzlast. Dann würde ich anders herum eine Annäherung vorschlagen, ähnlich wie this answer, aber einfacher.

1. Hashtable Lassen Ihre primäre Datenstruktur für die Datenspeicherung und den min-Heap eine Hilfsdatenstruktur sein, die aktuellen kleinsten Schlüssel in der Datenmenge zu halten.

2. Neuen Eintrag einfügen: Fügen Sie die Daten sowohl in die Hashtabelle als auch in den Min-Heap ein.

3. Aktualisieren Sie den Wert für den angegebenen Schlüssel: Aktualisieren Sie nur den Wert in der Hashtabelle.

4. Löschen Sie den Eintrag mit dem angegebenen Schlüssel: Löschen Sie den Eintrag mit dem angegebenen Schlüssel nur aus der Hashtabelle.

5. Zugriff auf den kleinsten Schlüssel: Wenn das Element am Anfang des Heaps nicht in der Hashtabelle gefunden wird, löschen Sie es; wiederholen, bis der oberste Schlüssel in der Hashtabelle vorhanden ist.