From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- heap.c | 291 ----------------------------------------------------------------- 1 file changed, 291 deletions(-) delete mode 100644 heap.c (limited to 'heap.c') diff --git a/heap.c b/heap.c deleted file mode 100644 index 091e761..0000000 --- a/heap.c +++ /dev/null @@ -1,291 +0,0 @@ -#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