Datastructure für die schnelle und effiziente Suche

Habe ich zum speichern der sortierten Daten in eine Datenstruktur.
Die Daten-Struktur, die ich verwenden möchten ist heap-oder im binären Suchbaum.
Aber ich bin verwirrt, die würde man besser auf die Voraussetzung, d.h. schnelle und effiziente Suche.

----MEHR DETAILS---

Bin ich eine Anwendung entwickeln, die Daten empfangen, die von einer Quelle(z.B. einem data-grid) und dann speichern Sie es in eine Datenstruktur. Die Daten, die vom Daten-GRID-station ist in der form von Ziffern sortiert. Die sortierten Daten können in aufsteigender oder absteigender Reihenfolge.

nun habe ich die Suche in den Daten. und der Prozess sollte effizient und schnell.

Helfen könnte: stackoverflow.com/questions/6147242/heap-vs-binary-search-tree
ich habe bereits überprüft, dass.. Es ist über die Speicherung von Daten in sortierter form. meine Anforderung ist die effiziente Suche. welche würde besser sein, wenn es um die Suche bestimmter Daten in datastructure.
beides sind gute Optionen, je nachdem, was einfach zu implementieren ist. wenn Sie die BST dann suchen AVL-Baum auch (BST-ist einfach zu implementieren und zu nutzen als heap nach mir)
Raman ist unten korrigieren. Für die Suche, die ich benutzen würde, BST, weil Sie bessere Leistungsfähigkeit haben, für beliebige Elemente. Obwohl, wenn Sie benötigen, ein max oder ein min-heap ist besser
Es gibt viele Datenstrukturen, wenn Sie spare-Speicher können Sie auch verwenden, Trie-Datenstruktur. Können Sie einfach posten Sie Ihre genaue Anforderung? Auf Ihrer Anforderung basieren, können wir wählen, werden die Daten-Strukturen

InformationsquelleAutor user3297557 | 2014-02-11

  1. 6

    Einem heap werden nur lassen Sie die Suche schnell für das minimale element (finden Sie es in O(1) Zeit, es zu entfernen in O(log n) Zeit). Wenn Sie es in die andere Richtung, es wird lassen Sie, finden Sie die maximale, aber nicht beides. Nach beliebigen Elementen suchen schnell (in O(log n) Zeit), Sie wollen der binäre Suchbaum.

    anyways Daten so sortiert, dass er durchqueren kann Sie durch die Liste, D. H., hängt von seiner Implementierung
    Gute Antwort. Ich würde ergänzen, es aber zu sagen, dass Sie vielleicht wollen, um auf einen ausgeglichenen binären Baum, je nach dem, was Sie wissen über die Daten. Das ist, wenn Ihre Daten in Ordnung, Ausgleich zur Aufrechterhaltung der Effizienz der Baum.
    Für mehr info siehe Skienna in algorist.com oder Suche nach "skiena algorithm design manual "pdf" zum Download der ersten Ausgabe.

    InformationsquelleAutor Raman Shah

  2. 3

    Für die effiziente Suche, man würde auf jeden Fall lieber einen binären Suchbaum.

    Zur Suche nach einem Wert in einem heap kann verlangen, dass Sie suchen, um den gesamten Baum - du kannst nicht garantieren, dass einige Wert kann nicht angezeigt werden entweder auf der linken oder rechten Teilbaum (es sei denn, eines der Kinder ist bereits größer als der Zielwert, aber das ist nicht garantiert passieren).

    So die Suche in einem heap in O(n), wo-wie es in O(log n) in eine (self-balancing) binären Suchbaum.

    Einem Haufen ist nur wirklich bevorzugt, wenn man in Erster Linie daran interessiert, und/oder entfernen der minimum /maximum, zusammen mit Einfügungen.

    Entweder konstruiert werden kann in O(n), wenn Sie gegeben sind, die bereits sortierten Daten.

    Erwähnten Sie eine sortierte Datenstruktur, sondern in die "weitere details" in deiner Frage sehe ich nicht wirklich, dass eine sortierte Datenstruktur erforderlich ist (es spielt keine Rolle, zu viel, das ist die form, in der Sie Ihre Daten bereits auf), aber es hängt wirklich davon ab, genau das, was Typ von Abfragen, die Sie tun.

    Wenn Sie nur gehst, um die Suche für die genauen Werte, die Sie nicht wirklich brauchen eine sortierte Datenstruktur, eine hash-Tabelle statt, die unterstützt, erwartet O(1) - lookups.

    Bauen Sie einen heap von beliebigen Daten (aber nicht unbedingt sortiert ist) O(n).
    Wahr (und nützliche Hinweis), es schien einfach wie eine unnötige detail an der Zeit zu schreiben, da die Eingabedaten bereits sortiert sind.

    InformationsquelleAutor Dukeling

  3. 1

    Lassen Sie mich eine Liste der möglichen Daten-Strukturen, und wir werden aufwändig:

    • Binären Suchbaum - es enthält sortiert die Daten, so dass das hinzufügen neuer Elemente ist aufwändig (O(log n) glaube ich). Wenn Sie suchen, durch Sie können Sie die binäre Suche ist O(log n). ES ist Speicher effizient, und es braucht nicht viel zusätzlichen Speicher.
    • Hash-Tabelle (http://en.wikipedia.org/wiki/Hash_table) - jedes element gespeichert ist, mit einem Hash. Sie können get-element, indem Sie die hash. Ihre Elemente müssen nicht sortiert werden, Sie brauchen nur hashing-Methode. Zugriff auf Elemente ist O(1), die ich vermute, ist ziemlich anständig 🙂

    Ich mich in der Regel verwenden, hashtables, aber es hängt davon ab, was genau Sie brauchen, um zu speichern und wie oft Sie hinzufügen oder löschen von Elementen.

    Überprüfen Sie auch dieses: Vorteile der Binären suchbäume über Hash-Tabellen

    Also meiner Meinung nach aus dem heap und binäre Suche Liste, verwenden Sie Hash-Tabelle.

    Ein BST erfordert O(n) Speicher, so auch die meisten anderen Strukturen, einschließlich eines hash-Tabelle - also ich bin mir nicht sicher, was du meinst mit "nicht brauchen zusätzlichen Speicher". Lookup in einer Hashtabelle in O(1) (nicht in O(n)), aber eine hash-Tabelle ist das nicht eine sortierte Datenstruktur, also vermutlich nicht entsprechen, OP-Anforderungen.
    Du hast Recht, weiß nicht, wie ich dies Schreibe 🙂

    InformationsquelleAutor Michał

  4. 1

    Ich würde mit hash-Tabelle mit separater Verkettung mit einem AVLTree (ich nehme an, Kollision). Es wird funktionieren, besser als O(logn), wobei n die Anzahl der Elemente. Nachdem man in den index-hash-Funktion, m Elemente werden in diesem index, wobei m kleiner oder gleich n ist. (Es ist in der Regel viel kleiner, aber nie mehr).
    O(1) für das hashing und O(logm) für die Suche in AVLTree. Dies ist schneller als die binäre Suche bei sortierten Daten.

    InformationsquelleAutor Boran YILDIRIM

Schreibe einen Kommentar