Gibt es einen Namen für die folgende Datenstruktur? Gibt es Papiere und Zitate?
Eine Möglichkeit, einen effizienten abstrakten Datentypen zu implementieren, ist es haben eine Sammlung von sortierten Arrays, wobei jedes Array eine einzigartige Größe von 2 hat.
Zum Beispiel kann eine Menge von 13 Elementen {1, 2, ..., 13} durch diese Sammlung sortierter Felder dargestellt werden: {[5], [2, 3, 9, 13], [1, 4, 6, 7, 8, 10, 11, 12]}.
Im Allgemeinen haben die Arrays, die in der Sammlung sind, Größen, die den 1 Bits in der binären Darstellung der Größe der Menge entsprechen. Die Datenstruktur ist effizient, da die Einfügung in amortisierten O (1) -Zeiten durchgeführt werden kann und die Suche in O (log n ) durchgeführt werden kann ) 2 ) Zeit (was besser ist als lineare Suche). Außerdem verwendet es im Gegensatz zu symmetrischen Binärbäumen und B-Bäumen, die O ( O ) verwenden, nur den Platzbedarf für O (log n ) > n ) zusätzlicher Platz für Zeiger. Daher wird fast der gesamte Speicherplatz für Nutzdaten verwendet.
Ich habe mir die Liste der Datenstrukturen angesehen, aber keine Übereinstimmung gefunden. Es stimmt, dass das Buch Einführung in Algorithmen ("CLRS") diese Datenstruktur als ein Hausaufgabe-Problem in der Sektion "Amortisierte Analyse" beschreibt, aber weil es eher eine Frage als ein Beispiel ist, sagt das Buch nicht viel darüber / p>
Eine ähnliche Idee stammt zumindest von Jean Vuillemins Originalveröffentlichung über Binomialhaufen im April 1978 Ausgabe von CACM. Ich würde erwarten, dass das Papier, das diese Datenstruktur eingeführt hat, von Vuillemin zitiert wird oder zitiert wird, aber keines der Papiere auf den Listen "Referenzen" und "zitiert nach" sieht vielversprechend aus.
Wenn ich Sie wäre, würde ich cstheory fragen und dann an CLRS schreiben, aber angesichts der suboptimalen Grenzen und des Fehlens der Löschung, I erwarten Sie nichts, bis die kurzweilige Datenstruktur -Gemeinschaft irgendwann Interesse geweckt hat.
Gibt es etwas Besonderes, das du wissen wolltest?
Tags und Links computer-science data-structures