Haufensort
Heap-Sortierung
Heap-Sortierung ist ein Sortieralgorithmus, der auf der Datenstruktur eines Heaps basiert und eine Auswahlsortierung ist. Die durchschnittliche Zeitkomplexität beträgt O (nlogn), was ebenfalls eine instabile Sortierung ist. Lassen Sie uns zunächst kurz die Heap-Struktur verstehen.
Heap
Ein Heap ist ein vollständiger Binärbaum mit den folgenden Eigenschaften: Der Wert jedes Knotens ist größer oder gleich zu seinen linken und rechten untergeordneten Knoten Der Wert eines Knotens wird als großer oberer Heap bezeichnet. Oder der Wert jedes Knotens ist kleiner oder gleich dem Wert seiner linken und rechten untergeordneten Knoten, was als kleiner oberer Heap bezeichnet wird.
Empfohlener Kurs: PHP-Tutorial.
Wie unten gezeigt:
Gleichzeitig nummerieren wir die Knoten im Heap schichtweise, um diese logische Struktur abzubilden Im Array sieht es so aus
Das Array ist logischerweise eine Heap-Struktur. Wir verwenden eine einfache Formel, um die Definition eines Heaps zu beschreiben:
Groß oberer Heap: arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
Kleiner oberer Heap: arr[i]
Die Grundidee der Heap-Sortierung ist:
Konstruieren Sie die zu seinde Sequenz sortiert Es bildet einen großen oberen Heap. Zu diesem Zeitpunkt ist der Maximalwert der gesamten Sequenz der Wurzelknoten an der Spitze des Heaps. Tauschen Sie es mit dem letzten Element aus, dann ist der letzte Wert der Maximalwert. Rekonstruieren Sie dann die verbleibenden n-1 Elemente in einen Heap, sodass der nächstkleinere Wert von n Elementen erhalten wird. Wenn Sie dies wiederholt ausführen, erhalten Sie eine geordnete Sequenz
Das obige ist der detaillierte Inhalt vonHaufensort. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Heiße KI -Werkzeuge
Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos
AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.
Undress AI Tool
Ausziehbilder kostenlos
Clothoff.io
KI-Kleiderentferner
AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.
Heißer Artikel
Heiße Werkzeuge
Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor
SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen
Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung
Dreamweaver CS6
Visuelle Webentwicklungstools
SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)
Heiße Themen
1379
52
Was ist der Unterschied zwischen Heap und Stack?
Nov 22, 2022 pm 04:12 PM
Unterschiede: 1. Der Heap-Speicherplatz wird im Allgemeinen vom Programmierer zugewiesen und freigegeben, während der Stapelspeicherplatz automatisch vom Betriebssystem zugewiesen und freigegeben wird. 2. Der Heap wird im Cache der zweiten Ebene gespeichert und sein Lebenszyklus wird durch den Garbage Collection-Algorithmus der virtuellen Maschine bestimmt, während der Stack den Cache der ersten Ebene verwendet, der sich beim Aufruf normalerweise im Speicherplatz befindet , und wird sofort nach Abschluss des Anrufs freigegeben. 3. Die Datenstrukturen sind unterschiedlich. Heap kann als Baum betrachtet werden, während Stack eine First-in-Last-out-Datenstruktur ist.
Deque in Python: Effiziente Warteschlangen und Stapel implementieren
Apr 12, 2023 pm 09:46 PM
Deque in Python ist eine hochoptimierte Low-Level-Deque, die für die Implementierung eleganter und effizienter Pythonic-Warteschlangen und -Stacks nützlich ist, die die häufigsten listenbasierten Datentypen in der Informatik sind. In diesem Artikel lernt Herr Yun Duo gemeinsam mit Ihnen Folgendes: Verwenden Sie Deque, um Elemente effektiv anzuzeigen und anzuhängen. Verwenden Sie Deque, um eine effiziente Warteschlange zu erstellen Ende einer Python-Liste und Popup-Elemente. Die Vorgänge sind im Allgemeinen sehr effizient. Wenn die Zeitkomplexität in Big O ausgedrückt wird, können wir sagen, dass es sich um O(1) handelt. Und wenn Python Speicher neu zuweisen muss, um die zugrunde liegende Liste zu vergrößern und neue Elemente aufzunehmen, sind diese
Der Unterschied zwischen Heap und Stack
Jul 18, 2023 am 10:17 AM
Der Unterschied zwischen Heap und Stack: 1. Die Speicherzuweisungsmethode ist unterschiedlich. Der Heap wird vom Programmierer manuell zugewiesen und freigegeben. 2. Die Größe ist unterschiedlich Der Stapel ist fest, während der Stapel vom Betriebssystem automatisch zugewiesen und freigegeben wird. 3. Die Datenzugriffsmethoden sind im Heap unterschiedlich, während der Datenzugriff im Stapel erfolgt Der Zugriff erfolgt über Variablennamen. 4. Datenlebenszyklus: Im Heap kann der Lebenszyklus von Daten sehr lang sein, während im Stapel der Lebenszyklus von Variablen durch den Bereich bestimmt wird, in dem sie sich befinden.
Was sind die Unterschiede zwischen Java-Heap und -Stack?
Dec 25, 2023 pm 05:29 PM
Der Unterschied zwischen Java-Heap und Stack: 1. Speicherzuweisung und -verwaltung; 3. Thread-Ausführung und Lebenszyklus; Detaillierte Einführung: 1. Der Java-Heap ist ein dynamisch zugewiesener Speicherbereich, der hauptsächlich zum Speichern von Objektinstanzen verwendet wird. Wenn ein Objekt erstellt wird, wird der entsprechende Speicher zugewiesen Speicherplatz auf dem System und automatische Speicherbereinigung und Speicherverwaltung. Die Größe des Heaps kann zur Laufzeit dynamisch angepasst, über JVM-Parameter konfiguriert usw. werden.
PHP-Datenstruktur: Das Geheimnis der Heap-Datenstruktur, die effiziente Sortierung und Prioritätswarteschlange realisiert
Jun 01, 2024 pm 03:54 PM
Die Heap-Datenstruktur in PHP ist eine Baumstruktur, die die vollständigen Binärbaum- und Heap-Eigenschaften erfüllt (der Wert des übergeordneten Knotens ist größer/kleiner als der Wert des untergeordneten Knotens) und mithilfe eines Arrays implementiert wird. Der Heap unterstützt zwei Vorgänge: Sortieren (Extrahieren des größten Elements von klein nach groß) und Prioritätswarteschlange (Extrahieren des größten Elements nach Priorität). Die Eigenschaften des Heaps werden über die Methoden heapifyUp bzw. heapifyDown verwaltet.
Heap und Prioritätswarteschlange in C++
Aug 22, 2023 pm 04:16 PM
Heap und Prioritätswarteschlange sind häufig verwendete Datenstrukturen in C++, und beide haben einen wichtigen Anwendungswert. In diesem Artikel werden der Heap und die Prioritätswarteschlange vorgestellt und analysiert, um den Lesern zu helfen, sie besser zu verstehen und zu verwenden. 1. Heap ist eine spezielle Baumdatenstruktur, mit der Prioritätswarteschlangen implementiert werden können. Im Heap erfüllt jeder Knoten die folgenden Eigenschaften: Sein Wert ist nicht kleiner (oder nicht größer) als der Wert seines übergeordneten Knotens. Seine linken und rechten Teilbäume sind ebenfalls ein Heap. Wir nennen einen Heap, der nicht kleiner als sein übergeordneter Knoten ist, einen „Min-Heap“ und einen Heap, der nicht größer als sein übergeordneter Knoten ist, einen „Max-Heap“.
Heap, Stack, Wörterbuch, Rot-Schwarz-Baum und andere Datenstrukturen in der Go-Sprache
Jun 03, 2023 pm 03:10 PM
Mit der Entwicklung der Informatik ist die Datenstruktur zu einem wichtigen Thema geworden. In der Softwareentwicklung sind Datenstrukturen sehr wichtig. Sie können die Effizienz und Lesbarkeit von Programmen verbessern und auch zur Lösung verschiedener Probleme beitragen. In der Go-Sprache sind auch Datenstrukturen wie Heap, Stack, Dictionary und Red-Black-Tree sehr wichtig. In diesem Artikel werden diese Datenstrukturen und ihre Implementierung in der Go-Sprache vorgestellt. Heap ist eine klassische Datenstruktur, die zur Lösung von Prioritätswarteschlangenproblemen verwendet wird. Eine Prioritätswarteschlange bezieht sich auf eine Warteschlange, in der Elemente entfernt werden
Was sind die Verwendungsszenarien von Heap und Prioritätswarteschlange in Python?
Oct 28, 2023 am 08:56 AM
Was sind die Verwendungsszenarien von Heap und Prioritätswarteschlange in Python? Der Heap ist eine spezielle binäre Baumstruktur, die häufig zur effizienten Verwaltung einer dynamischen Sammlung verwendet wird. Das Heapq-Modul in Python bietet eine Heap-Implementierung und kann problemlos Heap-Operationen ausführen. Eine Prioritätswarteschlange ist auch eine spezielle Datenstruktur. Im Gegensatz zu einer gewöhnlichen Warteschlange ist jedem Element eine Priorität zugeordnet. Das Element mit der höchsten Priorität wird zuerst entfernt. Das Heapq-Modul in Python kann auch die Prioritätswarteschlangenfunktion implementieren. Im Folgenden stellen wir einige vor