Funktion is_heap() implementiert.

1 files changed, 43 insertions, 0 deletions

diff --git a/heap.c b/heap.c
index 006ec57..ea33b16 100644
--- a/heap.c
+++ b/heap.c
@@ -1,3 +1,4 @@
+#include <assert.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -21,6 +22,8 @@ swap(T heap[], size_t i, size_t j)
         heap[j] = temp;
 }
 
+#define MAX_HEAP 1
+
 #if defined(MAX_HEAP)
 // MAX-HEAP Implementation
 static void
@@ -61,6 +64,24 @@ fixdown(T heap[], size_t i, size_t n)
                 i = m;
         }
 }
+
+static bool
+is_heap(T heap[], size_t n)
+{
+        for ( size_t i = 0; i < n / 2; ++i ) {
+                const size_t l = LEFT(i);
+                const size_t r = RIGHT(i);
+
+                if ( l < n && heap[i] < heap[l] ) {
+                        return false;
+                }
+                if ( r < n && heap[i] < heap[r] ) {
+                        return false;
+                }
+        }
+        return true;
+}
+
 #else
 // MIN-HEAP Implementation
 static void
@@ -101,6 +122,23 @@ fixdown(T heap[], size_t i, size_t n)
                 i = m;
         }
 }
+
+static bool
+is_heap(T heap[], size_t n)
+{
+        for ( size_t i = 0; i < n / 2; ++i ) {
+                const size_t l = LEFT(i);
+                const size_t r = RIGHT(i);
+
+                if ( l < n && heap[i] > heap[l] ) {
+                        return false;
+                }
+                if ( r < n && heap[i] > heap[r] ) {
+                        return false;
+                }
+        }
+        return true;
+}
 #endif
 
 static void
@@ -109,6 +147,8 @@ heapify(T heap[], size_t n)
         for ( size_t i = n / 2; i-- > 0; ) {
                 fixdown(heap, i, n);
         }
+
+        assert(is_heap(heap, n));
 }
 
 static void
@@ -239,12 +279,15 @@ main(void)
         // Kapitel 5.10, Seite 372 ff.
         T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 };
 
+        //heapify(heap, 10);
+        assert(is_heap(heap, 10));
         print_heap(heap, 10);
 
         //heap[10] = 13; fixup(heap, 10);
         swap(heap, 0, 9);
         fixdown(heap, 0, 9);
 
+        assert(is_heap(heap, 9));
         print_heap(heap, 9);
 #endif
 }