Wie eine Datenstruktur entwerfen, die eine Mischung aus hashtable ist und Heap

Question

Meine Frage, wie folgend:

eine Liste von Triple gegeben, und sie sind in einer Datenstruktur namens hash_heap gespeichert (Ich bin nicht sicher über die Name, ich meine nur, es sollte die Mischung aus Hashtabelle und Heap sein). Und ich hoffe, die Datenstruktur bietet folgende Methoden,

index_by_first_col(key) // the method could help find the a triple stored in it by matching the first column. It expects the searching is running at constant time 
get_min_by_third_col() // the method get the minimum triple sort according to the third column, it is also expects the method is running at constant time. 
insert_new_elt(triple) // add new trip, running at constant time 

Ist es möglich, einige Datenstruktur wie folgt zu implementieren? Ich weiß, Hashtable konnte die erste Methode unterstützen und Heap konnte die zweite und dritte Methode unterstützen, aber ich weiß nicht, wie man sie miteinander vermischt. Irgendwelche Ideen?

Danke!

Answer 1

Es gibt eine sehr einfache Datenstruktur, die Ihre angegebenen Anforderungen erfüllt.

Verwenden Sie eine Hash-Tabelle (eingegeben auf der ersten Spalte) und zusätzlich einen Zeiger auf Ihr minimales Element (durch die dritte Spalte). Dann ist index_by_first_col eine Hashtabellen-Suche, get_min_by_third_col ist eine Zeigerdereferenz und insert_new_elt ist eine Hashtabelleneinfügung und ein Vergleich, um festzustellen, ob der Minzeiger aktualisiert werden muss.

Beachten Sie, dass dies O (n) Löschung (des Minimums) gibt, aber Sie keine Anforderungen an das Löschen angegeben haben.