Commits

Anonymous committed 95bcefa

add heap.h, demo heap and priority queue

  • Participants
  • Parent commits ab4a8b3

Comments (0)

Files changed (4)

File types/demo.c

 #include <stdio.h>
+#include <stdlib.h>
 #include "vector.h"
 #include "list.h"
+#include "heap.h"
 
 vector_def(Stack, int) // use vector as stack
 list_def  (Listn, int) // use list node as list
+heap_def  (Max_heap, int, a < b)
 
+#define LENGTH(x) (sizeof(x) / sizeof(*x))
 int main(void)
 {
     /* Vector demo */
         printf("%d\n", p->data);
     Listn_del_all(head);
 
+    /* Heap demo */
+    size_t j;
+    int b[] = { 3, 5, 2, 3, 8, 0 };
+    size_t n = LENGTH(b) - 1;
+    printf("is %sa heap\n", Max_heap_is_heap(b, n) ? "" : "not ");
+    Max_heap_heapify(b, n);
+    Max_heap_push(b, n++, 7);
+    printf("is %sa heap\n", Max_heap_is_heap(b, n) ? "" : "not ");
+    for (j = 0; j < LENGTH(b); j++)
+        printf("%d%c", Max_heap_pop(b, n--), (j + 1 == LENGTH(b)) ? '\n' : ',');
+
+    int a[] = { 3, 5, 2, 3, 4 };
+    for (j = 0; j < LENGTH(a); j++)
+        printf("%d%c", a[j], (j + 1 == LENGTH(a)) ? '\n' : ',');
+    Max_heap_sort(a, LENGTH(a));
+    for (j = 0; j < LENGTH(a); j++)
+        printf("%d%c", a[j], (j + 1 == LENGTH(a)) ? '\n' : ',');
+
+    /* Using Vector and Heap to make a priority queue */
+    Stack *v = Stack_new(0);
+    i = j = 20;
+    while (i--) // Initial members
+        Stack_push(v, rand() % j);
+    Max_heap_heapify(v->data, v->size);
+    i = 20;
+    while (i--) { // add more members
+        Stack_push(v, 0); // make space
+        Max_heap_push(v->data, v->size - 1, rand() % j); // place the member
+    }
+    while (v->size) {
+        printf("%d\n", Max_heap_pop(v->data, v->size)); // get the member
+        Stack_pop(v); // remove it's place
+    }
+    printf("empty size:%zu\n", v->size);
+    Stack_del(v);
+
     return 0;
 }

File types/heap.h

+#ifndef HEAP_H_
+#define HEAP_H_
+
+#define heap_def(Name, Type, Cmp)                                \
+static inline int Name##_cmp(Type a, Type b)                     \
+{                                                                \
+    return Cmp;                                                  \
+}                                                                \
+void Name##_sift_down(Type *b, size_t top, size_t bot)           \
+{                                                                \
+    size_t c;                                                    \
+    for (; top * 2 + 1 <= bot; top = c) {                        \
+        Type t;                                                  \
+        c = top * 2 + 1;                                         \
+        if (c + 1 <= bot && Name##_cmp(b[c], b[c + 1]))          \
+            c++;                                                 \
+        if (Name##_cmp(b[c], b[top]))                            \
+            return;                                              \
+        t      = b[c  ];                                         \
+        b[c  ] = b[top];                                         \
+        b[top] = t;                                              \
+    }                                                            \
+}                                                                \
+void Name##_sift_up(Type *b, size_t top, size_t bot)             \
+{                                                                \
+    size_t c, p;                                                 \
+    for (c = bot; c > top; c = p) {                              \
+        p = (c - 1) / 2;                                         \
+        if (Name##_cmp(b[p], b[c])) {                            \
+            Type t = b[p];                                       \
+            b[p]   = b[c];                                       \
+            b[c]   = t;                                          \
+        } else                                                   \
+            return;                                              \
+    }                                                            \
+}                                                                \
+int Name##_is_heap(Type *b, size_t n)                            \
+{                                                                \
+    size_t i;                                                    \
+    for (i = 1; i < n && !Name##_cmp(b[(i - 1) / 2], b[i]); ++i) \
+        ;                                                        \
+    return (i == n);                                             \
+}                                                                \
+void Name##_heapify(Type *b, size_t n)                           \
+{                                                                \
+    size_t top;                                                  \
+    for (top = (n - 2) / 2; top < n; top--)                      \
+        Name##_sift_down(b, top, n - 1);                         \
+}                                                                \
+Type Name##_pop(Type *b, size_t n)                               \
+{                                                                \
+    Type r = b[0];                                               \
+    b[0] = b[--n];                                               \
+    if (n)                                                       \
+        Name##_sift_down(b, 0, n - 1);                           \
+    return r;                                                    \
+}                                                                \
+void Name##_push(Type *b, size_t n, Type t)                      \
+{                                                                \
+    b[n++] = t;                                                  \
+    Name##_sift_up(b, 0, n - 1);                                 \
+}                                                                \
+void Name##_sort(Type *b, size_t n)                              \
+{                                                                \
+    size_t bot;                                                  \
+    Name##_heapify(b, n);                                        \
+    for (bot = n - 1; bot > 0; Name##_sift_down(b, 0, --bot)) {  \
+        Type t = b[  0];                                         \
+        b[  0] = b[bot];                                         \
+        b[bot] = t;                                              \
+    }                                                            \
+}
+
+#endif

File types/list.h

 
 #include <stdlib.h>
 
-/*
- * NOTES
- * Circular doubly linked list.
- * Insert and append add before and after the given node respectively. This has
- * the consequence that insert and append on a head will append and insert on
- * the list as a whole, respectively.
- */
 #define list_def(Name, Type)         \
-typedef struct Name_ Name;           \
-struct Name_{                        \
+typedef struct Name##_ Name;         \
+struct Name##_ {                     \
     Type  data;                      \
     Name *next;                      \
     Name *prev;                      \

File types/vector.h

 #define VECTOR_H_
 
 #include <stdlib.h>
-#include <assert.h>
 #include <sys/types.h>
 
-size_t size_t_min(size_t a, size_t b) { return a < b ? a : b; }
-size_t size_t_max(size_t a, size_t b) { return a > b ? a : b; }
+static inline size_t size_t_min(size_t a, size_t b) { return a < b ? a : b; }
+static inline size_t size_t_max(size_t a, size_t b) { return a > b ? a : b; }
 
 #define vector_def(Name, Type)                                       \
 typedef struct {                                                     \
 Type Name##_pop(Name *v)                                             \
 {                                                                    \
     Type t;                                                          \
-    assert(v->size > 0);                                             \
     t = v->data[--v->size];                                          \
     if (v->size <= v->capacity / 4 && v->capacity > v->min_capacity) \
         Name##_resize(v, size_t_max(v->size * 2, v->min_capacity));  \