min-/max-heap

1 files changed, 51 insertions, 1 deletions

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");
 }