From 15f76faad1ea8b13294e08fdf8f95e8f7df4cae1 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 29 Nov 2020 16:52:05 +0100 Subject: Funktion is_heap() implementiert. --- heap.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) (limited to 'heap.c') diff --git a/heap.c b/heap.c index 006ec57..ea33b16 100644 --- a/heap.c +++ b/heap.c @@ -1,3 +1,4 @@ +#include #include #include #include @@ -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 } -- cgit v1.3