1 files changed, 291 insertions, 0 deletions

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 <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#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
+}