From d8fa41d3f56640dcf3b59b9555d9a74d88fd48ca Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 29 Nov 2020 09:36:16 +0100
Subject: min-/max-heap

---
 heap.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 51 insertions(+), 1 deletion(-)

(limited to 'heap.c')

diff --git a/heap.c b/heap.c
index 7e0f64e..3e354c4 100644
--- a/heap.c
+++ b/heap.c
@@ -21,6 +21,8 @@ swap(T heap[], size_t i, size_t j)
 	heap[j] = temp;
 }
 
+#if defined(MAX_HEAP)
+// MAX-HEAP Implementation
 static void
 fixup(T heap[], size_t i)
 {
@@ -59,6 +61,47 @@ fixdown(T heap[], size_t i, size_t n)
 		i = m;
 	}
 }
+#else
+// MIN-HEAP Implementation
+static void
+fixup(T heap[], size_t i)
+{
+	size_t p = PARENT(i);
+
+	while ( i > 0 && heap[i] < heap[p] ) {
+		swap(heap, i, p);
+
+		i = p;
+		p = PARENT(i);
+	}
+}
+
+static void
+fixdown(T heap[], size_t i, size_t n)
+{
+	for ( ;; ) {
+		const size_t l = LEFT(i);
+		const size_t r = RIGHT(i);
+		size_t       m = i;
+
+		if ( l < n && heap[l] < heap[m] ) {
+			m = l;
+		}
+
+		if ( r < n && heap[r] < heap[m] ) {
+			m = r;
+		}
+
+		if ( m == i ) {
+			break;
+		}
+
+		swap(heap, m, i);
+
+		i = m;
+	}
+}
+#endif
 
 static void
 heapify(T heap[], size_t n)
@@ -136,7 +179,7 @@ print_heap(T heap[], size_t n)
 void
 test_heapsort(void)
 {
-	static const size_t N = 1001;
+	static const size_t N = 1000000;
 	T                   array[N];
 
 	puts("fülle....");
@@ -150,10 +193,17 @@ test_heapsort(void)
 
 	puts("teste...");
 	for ( size_t idx = 1; idx != NELEM(array); ++idx ) {
+#if defined(MAX_HEAP)
 		if ( array[idx - 1] > array[idx] ) {
 			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
 			exit(EXIT_FAILURE);
 		}
+#else
+		if ( array[idx - 1] < array[idx] ) {
+			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
+			exit(EXIT_FAILURE);
+		}
+#endif
 	}
 	puts("ok");
 }
-- 
cgit v1.3