From 28d9e48724cd0f0748fea5e0a24e57c92caa2a4c Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 29 Nov 2020 19:04:47 +0100
Subject: bottom-up-heapsort hinzugefügt.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 heap.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 64 insertions(+), 2 deletions(-)

(limited to 'heap.c')

diff --git a/heap.c b/heap.c
index 4d4fcc8..6233cf2 100644
--- a/heap.c
+++ b/heap.c
@@ -162,7 +162,68 @@ my_heapsort(T a[], size_t n)
 	}
 }
 
-// TODO: https://www.geeksforgeeks.org/how-to-check-if-a-given-array-represents-a-binary-heap/
+void
+heapsort_bu(T *data, int n) // zu sortierendes Feld und seine Länge
+{
+	T   val;
+	int parent, child;
+	int root = n >> 1; // erstes Blatt im Baum
+
+	for ( ;; ) {
+		if ( root ) { // Teil 1: Konstruktion des Heaps
+			parent = --root;
+			val    = data[root]; // zu versickernder Wert
+		}
+		else if ( --n ) {      // Teil 2: eigentliche Sortierung
+			val     = data[n]; // zu versickernder Wert vom Heap-Ende
+			data[n] = data[0]; // Spitze des Heaps hinter den Heap in
+			parent  = 0;       //   den sortierten Bereich verschieben
+		}
+		else // Heap ist leer; Sortierung beendet
+			break;
+
+		while ( (child = (parent + 1) << 1) < n ) // zweites (!) Kind;
+		{                                         // Abbruch am Ende des Heaps
+			if ( data[child - 1] > data[child] )  // größeres Kind wählen
+				--child;
+
+			data[parent] = data[child]; // größeres Kind nach oben rücken
+			parent       = child;       // in der Ebene darunter weitersuchen
+		}
+
+		if ( child == n )                   // ein einzelnes Kind am Heap-Ende
+		{                                   //   ist übersprungen worden
+			if ( data[--child] >= val ) {   // größer als der zu versick-
+				data[parent] = data[child]; //   ernde Wert, also noch nach oben
+				data[child]  = val;         // versickerten Wert eintragen
+				continue;
+			}
+
+			child = parent; // 1 Ebene nach oben zurück
+		}
+		else {
+			if ( data[parent] >= val ) { // das Blatt ist größer als der
+				data[parent] = val;      //   zu versickernde Wert, der damit
+				continue;                //   direkt eingetragen werden kann
+			}
+
+			child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück
+		}
+
+		while ( child != root ) // maximal zum Ausgangspunkt zurück
+		{
+			parent = (child - 1) >> 1; // den Vergleichswert haben wir bereits
+			                           //   nach oben verschoben
+			if ( data[parent] >= val ) // größer als der zu versickernde
+				break;                 //   Wert, also Position gefunden
+
+			data[child] = data[parent]; // Rückverschiebung nötig
+			child       = parent;       // 1 Ebene nach oben zurück
+		}
+
+		data[child] = val; // versickerten Wert eintragen
+	}
+}
 
 // -------------------------------------------
 
@@ -232,7 +293,8 @@ test_heapsort(void)
 
 	puts("sortiere....");
 	clock_t start = clock();
-	my_heapsort(array, NELEM(array));
+	//my_heapsort(array, NELEM(array));
+	heapsort_bu(array, NELEM(array));
 	clock_t end = clock();
 
 	puts("teste...");
-- 
cgit v1.3