Algorithmus-Auffrischung. Warum ist Heapsort ein Insort-Algorithmus?

15

Ich kann nicht verstehen, warum der Heapsort als Inplace- Sortieralgorithmus angesehen wird.

Ich meine, eine zusätzliche Datenstruktur, die mit den Elementen des zu sortierenden Arrays gefüllt ist, dh ein Heap, wird verwendet, um die Extraktion des min-Werts und den Sortiervorgang zu unterstützen.

Kann es sein, dass ich die Definition von Inplace hier falsch verstehe?

Aber Einfügesortierung zum Beispiel ist offensichtlich, dass es sich um einen Inplace-Algorithmus handelt, dh es wird kein zusätzlicher Speicher für die Elemente benötigt.

Warum wird es als vorhanden betrachtet?

user10326
quelle

Antworten:

12

Ich meine, eine zusätzliche Datenstruktur, die mit den Elementen des zu sortierenden Arrays gefüllt ist, dh ein Heap, wird verwendet, um die Extraktion des min-Werts und den Sortiervorgang zu unterstützen.

Nein. Das Array wird transformiert, um der Heap-Beschränkung zu entsprechen, ohne mehr als O (1) zusätzlichen Speicher zu verwenden. (Alles, was Sie brauchen, ist zusätzlicher Speicher, der ausreicht, um ein Element des Arrays für Swap-Zwecke sowie einen oder zwei Boolesche Werte und eine oder zwei Schleifenvariablen aufzunehmen.)

Ok, technisch gesehen kann es sein, dass Heapsort normalerweise so erklärt wird, als würde es einen separaten Heap verwenden, aber es ist durchaus möglich, ihn direkt zu implementieren.

Peter Taylor
quelle
3
Der einzige Ort, an dem ich erwartet hätte, dass "heapsort" mit einem separaten Heap (im Code) angezeigt wird, ist eine funktionale Sprache wie Haskell, aus dem gleichen Grund, dass das übliche funktionale "Quicksort" nicht auch vorhanden ist - funktionale Programmierer wie Ihre Listen sind sehr häufig, und eine In-Place-Sortierung ist statusbehaftet - sie ändert den Status des Arrays / was auch immer die Daten enthalten. Angst-Anführungszeichen, weil ich nicht wirklich akzeptiere, dass eine fehlgeleitete Quicksortierung überhaupt eine Quicksortierung ist oder dass eine fehlgeleitete Heapsortierung überhaupt eine Heapsortierung ist - zumindest nicht ohne klar zu sagen, dass es nicht in Ordnung ist. Platz.
Steve314
1
@ Steve314, ich glaube, ich habe etwas Lehrmaterial gesehen, das etwas in der Art aussagt, wie man "es auf einen Haufen legt und dann die Elemente nacheinander herauszieht und sie in ein Array legt". Aber nachdem ich gerade CLR überprüft habe, kann ich berichten, dass sie eine In-Place-Version anzeigen.
Peter Taylor
2
@PeterTaylor: Ja, in dem Buch, das ich gerade gelesen habe (Skiena), wurde Heapsort präsentiert, indem ein zusätzlicher Heap gebaut wurde.
user10326
4

Möglicherweise fehlt Ihnen das grundlegende Verständnis, dass ein Array zum Festlegen des Layouts eines Baums verwendet werden kann.

Angenommen, Sie haben einen Binärbaum und ein innerer Knoten befindet sich am Index i des Arrays. Dann kann der Array-Index des übergeordneten und untergeordneten Elements dieses Knotens wie folgt ermittelt werden:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Sehen:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Da der Heap vollständig in einem Array verwaltet und organisiert werden kann, kann Heapsort an Ort und Stelle ausgeführt werden, indem Elemente innerhalb des Eingabearrays verschoben werden. In der Tat wird der Heap mithilfe des ursprünglichen Eingabearrays erstellt und bearbeitet.

stackoverflowuser2010
quelle
: Ich weiß darüber Bescheid. Die Probleme scheinen zu sein, dass das Buch, das ich lese, Heapsort mit einem separaten Heap präsentiert. Ich habe nicht verstanden oder geglaubt, dass diese Präsentation das Verständnis des Algorithmus erleichtern soll (vielleicht? Nicht sicher, warum?) so präsentiert)
user10326
Ich würde Ihnen wärmstens empfehlen, das Buch "Introduction to Algorithms" von Cormen et al. Es werden alle algorithmischen Fragen eindeutig beantwortet. Wenn Sie es ernst meinen mit einer Karriere als Informatiker oder Softwareentwickler, dann brauchen Sie dieses Buch.
stackoverflowuser2010
1

Wenn man, wie Sie sagen, wirklich eine zusätzliche Struktur benötigt, um den Heap zu erstellen, dann wäre heapsort in der Tat KEIN Inplace-Sortieralgorithmus.

Dies ist jedoch nicht der Fall. Sie können den Heap auf demselben Array erstellen, das Sie sortieren möchten, und anschließend den Heapsort-Algorithmus anwenden, sodass er an Ort und Stelle sortiert wird.

Daniel Scocco
quelle
Grundsätzlich gibt es einen "Heapify" -Algorithmus, mit dem Daten in einem Array neu angeordnet werden, sodass sie den Regeln eines Heaps in IIRC O (n) -Zeit entsprechen. Den Pseudocode finden Sie unter programmers.stackexchange.com/questions/116904/… . Danach ist es meistens eine Sache, wiederholte Heap-Root-Extrakte zu machen und zu verfolgen, wie viel des Arrays noch "Heap" ist und wie viel das Endergebnis sortiert.
Steve314
0

In der Informatik ist ein In-Place-Algorithmus (oder lateinisch in situ) ein Algorithmus, der Eingaben unter Verwendung einer Datenstruktur mit einer kleinen, konstanten Menge zusätzlichen Speicherplatzes umwandelt. Die Eingabe wird normalerweise durch die Ausgabe überschrieben, wenn der Algorithmus ausgeführt wird. Ein Algorithmus, der nicht vorhanden ist, wird manchmal als nicht vorhanden oder nicht vorhanden bezeichnet.

Wikipedia - In-Place-Algorithmus

Rein Henrichs
quelle
Warum wird Mergesort dann als nicht vorhandener Algorithmus betrachtet?
user10326
3
Dies ist keine nützliche Antwort. Es hat nichts mit Heapsort zu tun und beantwortet die Frage nicht.
Stackoverflowuser2010
Natürlich hat es etwas mit Heapsort zu tun. Heapsort ist ein direkter Sortieralgorithmus, wie sich aus der Definition ergibt. In der Tat wurde es von der Heapsort-Seite verlinkt.
Rein Henrichs
0

Es wird als vorhanden betrachtet, da der Platzbedarf vernachlässigbar ist (konstant oder überhaupt nicht, wenn Sie bitweise Operationen zum Austauschen von Elementen verwenden). MergeSort ist beispielsweise nicht vorhanden, da die Eingabemenge nicht bei jeder Iteration des Suchbeispiels geändert wird.

Der beste Weg, um die Unterschiede zwischen In-Place-Algorithmen und Out-Of-Place-Algorithmen zu veranschaulichen, besteht wahrscheinlich darin, den folgenden C / C ++ - String-Umkehrcode zu betrachten, der dies ausführt (von K & R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Wenn Sie beispielsweise die Eingabezeichenfolge vom Ende aus lesen und die Zeichen in einem anderen Puffer ablegen würden, wäre dies ein fehl am Platz befindlicher Algorithmus zur Umkehrung der Zeichenfolge.

rdasxy
quelle
1
Mergesort ist verdammt nervig - man kann sich leicht zu Unrecht davon überzeugen, dass man eine Strategie verfolgt. Normalerweise funktioniert es nur für kleine Arrays. Aber ich denke , ich ein Papier einmal heruntergeladen , wo jemand tat Arbeit aus einer direkten Variante des Merge-Sortieralgorithmus. Ich werde sehen, ob ich es wieder finde.
Steve314