add: graphs et rushs

7 files changed, 177 insertions, 0 deletions

diff --git a/rushs/evalexpr/heap/Makefile b/rushs/evalexpr/heap/Makefile
new file mode 100644
index 0000000..2ed972b
--- /dev/null
+++ b/rushs/evalexpr/heap/Makefile
@@ -0,0 +1,14 @@
+CC = gcc
+CFLAGS = -Wall -Werror -Wvla -Wextra -std=c99 -pedantic
+SRC = add.c del.c print.c pop.c create.c
+OBJ = $(SRC:.c=.o)
+
+.PHONY: library clean
+
+library: $(OBJ)
+	ar csr libheap.a $(OBJ)
+
+$(OBJ): $(SRC)
+
+clean:
+	$(RM) libheap.a $(OBJ)
diff --git a/rushs/evalexpr/heap/add.c b/rushs/evalexpr/heap/add.c
new file mode 100644
index 0000000..78a4db8
--- /dev/null
+++ b/rushs/evalexpr/heap/add.c
@@ -0,0 +1,39 @@
+#include <stdlib.h>
+
+#include "heap.h"
+
+void heapify(int arr[], int n, int i)
+{
+    if (i == 0)
+        return;
+    int parent = (i - 1) / 2;
+    if (parent >= 0)
+    {
+        if (arr[i] > arr[parent])
+        {
+            int tmp = arr[i];
+            arr[i] = arr[parent];
+            arr[parent] = tmp;
+            heapify(arr, n, parent);
+        }
+    }
+}
+
+void add(struct heap *heap, int val)
+{
+    if (heap->size == heap->capacity)
+    {
+        heap->array = realloc(heap->array, heap->capacity * 2 * sizeof(int));
+        if (heap->array == NULL)
+        {
+            free(heap);
+            return;
+        }
+        heap->capacity *= 2;
+    }
+
+    heap->array[heap->size] = val;
+    heap->size++;
+
+    heapify(heap->array, heap->size, heap->size - 1);
+}
diff --git a/rushs/evalexpr/heap/create.c b/rushs/evalexpr/heap/create.c
new file mode 100644
index 0000000..f0675ad
--- /dev/null
+++ b/rushs/evalexpr/heap/create.c
@@ -0,0 +1,19 @@
+#include <stdlib.h>
+
+#include "heap.h"
+
+struct heap *create_heap(void)
+{
+    struct heap *res = malloc(sizeof(struct heap));
+    if (res == NULL)
+        return NULL;
+    res->size = 0;
+    res->capacity = 8;
+    res->array = malloc(8 * sizeof(int));
+    if (res->array == NULL)
+    {
+        free(res);
+        return NULL;
+    }
+    return res;
+}
diff --git a/rushs/evalexpr/heap/del.c b/rushs/evalexpr/heap/del.c
new file mode 100644
index 0000000..4d2ae35
--- /dev/null
+++ b/rushs/evalexpr/heap/del.c
@@ -0,0 +1,9 @@
+#include <stdlib.h>
+
+#include "heap.h"
+
+void delete_heap(struct heap *heap)
+{
+    free(heap->array);
+    free(heap);
+}
diff --git a/rushs/evalexpr/heap/heap.h b/rushs/evalexpr/heap/heap.h
new file mode 100644
index 0000000..085f436
--- /dev/null
+++ b/rushs/evalexpr/heap/heap.h
@@ -0,0 +1,20 @@
+#ifndef HEAP_H
+#define HEAP_H
+
+// size_t
+#include <stddef.h>
+
+struct heap
+{
+    size_t size;
+    size_t capacity;
+    int *array;
+};
+
+struct heap *create_heap(void);
+void add(struct heap *heap, int val);
+int pop(struct heap *heap);
+void delete_heap(struct heap *heap);
+void print_heap(const struct heap *heap);
+
+#endif /* !HEAP_H */
diff --git a/rushs/evalexpr/heap/pop.c b/rushs/evalexpr/heap/pop.c
new file mode 100644
index 0000000..55e063f
--- /dev/null
+++ b/rushs/evalexpr/heap/pop.c
@@ -0,0 +1,49 @@
+#include <assert.h>
+#include <stdlib.h>
+
+#include "heap.h"
+
+void heapify2(struct heap *h, size_t i)
+{
+    size_t max = i;
+    if (2 * i + 1 < h->size && h->array[2 * i + 1] > h->array[max])
+        max = 2 * i + 1;
+    if (2 * i + 2 < h->size && h->array[2 * i + 2] > h->array[max])
+        max = 2 * i + 2;
+    if (max != i)
+    {
+        int tmp = h->array[i];
+        h->array[i] = h->array[max];
+        h->array[max] = tmp;
+        heapify2(h, max);
+    }
+}
+
+int pop(struct heap *heap)
+{
+    assert(heap->size != 0);
+    if (heap->size == 1)
+    {
+        heap->size--;
+        return heap->array[0];
+    }
+    else
+    {
+        int res = heap->array[0];
+        heap->array[0] = heap->array[heap->size - 1];
+        heap->size--;
+        heapify2(heap, 0);
+        if (heap->size < heap->capacity / 2 && heap->capacity > 8)
+        {
+            heap->array =
+                realloc(heap->array, (heap->capacity / 2) * sizeof(int));
+            if (heap->array == NULL)
+            {
+                free(heap);
+                return -1;
+            }
+            heap->capacity /= 2;
+        }
+        return res;
+    }
+}
diff --git a/rushs/evalexpr/heap/print.c b/rushs/evalexpr/heap/print.c
new file mode 100644
index 0000000..f5bbe95
--- /dev/null
+++ b/rushs/evalexpr/heap/print.c
@@ -0,0 +1,27 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "heap.h"
+
+void print_rec(const struct heap *h, size_t i, int root)
+{
+    if (i >= h->size)
+        return;
+    if (!root)
+        printf(" ");
+    else
+        root = 0;
+    printf("%d", h->array[i]);
+    if (i == h->size - 1)
+    {
+        return;
+    }
+    print_rec(h, i * 2 + 1, root);
+    print_rec(h, i * 2 + 2, root);
+}
+
+void print_heap(const struct heap *heap)
+{
+    print_rec(heap, 0, 1);
+    printf("\n");
+}