Priority Queue basierend auf 2-3-4 Baumstruktur

Hat jemand Informationen über priority queues basierend auf der 2-4 tree structure? Ich habe den ganzen Tag gesucht .. Alle Referenzen von jedem, der weiß, wäre wirklich geschätzt .. Vielen Dank.Priority Queue basierend auf 2-3-4 Baumstruktur

Quelle

2011-01-16 alhid

Ist dies mit [Min-Max-Heaps] (http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node11.html) verbunden? – finnw

@finnw: nicht direkt. Prioritätswarteschlangen können unter Verwendung einer beliebigen standardisierten geordneten Suchdatenstruktur (2-3-4 Bäume, BSTs, Rot-Schwarz-Bäume usw.) implementiert werden. Die Struktur, zu der Sie eine Verknüpfung herstellen, ist eine spezielle Datenstruktur für dieses Problem. –

Sehr interessante und seltene Datenstruktur. Ich lese das CLRS-Buch 'Einführung in Algorithmen'. 2-4 Bäume sind sehr gut erklärt. Ich denke, jedes Blatt muss nur einen Wert in der Warteschlange enthalten. – alhid

Implementieren Sie 2-3-4 Bäume, so dass doppelte Schlüssel möglich sind.
Verwenden Sie diese als Prioritätswarteschlangen, indem Sie Prioritäten als Schlüssel speichern und das Minimum- (oder Maximum-) Element retrieve + delete implementieren. Das Minimum kann gefunden werden, indem Sie dem untersten untergeordneten Zeiger folgen, bis er null wird.

Siehe auch tree sort.

Quelle

2011-01-16 18:56:43

Hmmm ich werde das versuchen. Vielen Dank!! – alhid

Priority Queue basierend auf 2-3-4 Baumstruktur

Antwort

Verwandte Themen