From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- src/heap.c | 291 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 291 insertions(+) create mode 100644 src/heap.c (limited to 'src/heap.c') diff --git a/src/heap.c b/src/heap.c new file mode 100644 index 0000000..091e761 --- /dev/null +++ b/src/heap.c @@ -0,0 +1,291 @@ +#include +#include +#include +#include +#include + +#include "util.h" + +typedef int T; + +// https://stackoverflow.com/a/22900767 + +#define LEFT(idx) (idx * 2 + 1) +#define RIGHT(idx) (idx * 2 + 2) +#define PARENT(idx) ((idx - 1) / 2) + +static void +swap(T heap[], size_t i, size_t j) +{ + T temp = heap[i]; + heap[i] = heap[j]; + heap[j] = temp; +} + +#define MAX_HEAP 1 + +#if defined(MAX_HEAP) +// MAX-HEAP Implementation +static void +fixup(T heap[], size_t i) +{ + size_t p = PARENT(i); + + while ( i > 0 && heap[p] < heap[i] ) { + swap(heap, p, i); + + 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[m] < heap[l] ) { + m = l; + } + + if ( r < n && heap[m] < heap[r] ) { + m = r; + } + + if ( m == i ) { + break; + } + + swap(heap, m, i); + + 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 +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; + } +} + +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 +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 +my_heapsort(T a[], size_t n) +{ + heapify(a, n); + + while ( n-- ) { + swap(a, 0, n); + fixdown(a, 0, n); + } +} + +// ------------------------------------------- + +struct pq { // Priority Queue + T heap[251]; + size_t sz; +}; + +void +pq_init(struct pq *pq) +{ + pq->sz = 0; +} + +bool +pq_push(struct pq *pq, T data) +{ + if ( pq->sz == NELEM(pq->heap) ) { + return false; + } + + pq->heap[pq->sz] = data; + fixup(pq->heap, pq->sz); + ++pq->sz; + return true; +} + +bool +pq_pop(struct pq *pq, T *data) +{ + if ( pq->sz == 0 ) { + return false; + } + + *data = pq->heap[0]; + --pq->sz; + pq->heap[0] = pq->heap[pq->sz]; + fixdown(pq->heap, 0, pq->sz); + return true; +} + +// ------------------------------------------- + +void +print_heap(T heap[], size_t n) +{ + if ( n ) { + printf("%d", heap[0]); + for ( size_t i = 1; i != n; ++i ) { + printf(", %d", heap[i]); + } + putchar('\n'); + } +} + +void +test_heapsort(void) +{ + static const size_t N = 1000000; + T array[N]; + + puts("fülle...."); + srand(time(NULL)); + for ( size_t idx = 0; idx != NELEM(array); ++idx ) { + array[idx] = rand(); + } + + puts("sortiere...."); + clock_t start = clock(); + my_heapsort(array, NELEM(array)); + clock_t end = clock(); + + 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 + } + printf("ok! (%.3lf sec)\n", ((double) end - start) / CLOCKS_PER_SEC); +} + +void +test_pq(void) +{ + struct pq pq[1]; + + pq_init(pq); + + for ( int i = 0; i != 10; ++i ) { + pq_push(pq, rand()); + } + + T data; + while ( pq_pop(pq, &data) ) { + printf("%d\n", data); + } +} + +int +main(void) +{ + test_heapsort(); + test_pq(); +#if 1 // Heap-Testprogramm + // Beispiel aus "Informatik - Datenstrukturen und Konzepte der Abstraktion" + // 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