feat: add heap in c

1 files changed, 103 insertions, 0 deletions

diff --git a/2_anno/Algoritmi/data_structures/heap.c b/2_anno/Algoritmi/data_structures/heap.c
new file mode 100644
index 0000000..56c3d3d
--- /dev/null
+++ b/2_anno/Algoritmi/data_structures/heap.c
@@ -0,0 +1,103 @@
+#include<stdio.h>
+#include<stdlib.h>
+#define HEAP_TYPE 0 // if 0 is max heap, else min heap
+
+unsigned heapsize = 0;
+
+int compare(int x, int y) {
+    return (HEAP_TYPE) ? x < y : x > y;
+}
+
+void swap(int* a, int x, int y) {
+    int temp = a[x];
+    a[x] = a[y];
+    a[y] = temp;
+}
+
+void insert(int* a, int k) {
+    a[++heapsize] = k;
+    unsigned i = heapsize;
+
+    while(i > 1 && compare(a[i>>1], a[i])) {
+        swap(a, i, i >> 1);
+        i >>= 1;
+    }
+}
+
+void heapify(int* a, int n, int i) {
+    int l = i << 1;
+    int r = l | 1;
+
+    int max = i;
+    if(l <= n && compare(a[l], a[max])) max = l;
+    if(r <= n && compare(a[r], a[max])) max = r;
+
+    if(max != i) {
+        swap(a, i, max);
+        heapify(a, n, max);
+    }
+}
+
+void build(int* a, int n) {
+    for(unsigned i = n/2; i > 0; --i) {
+        heapify(a, n, i);
+    }
+}
+
+int extract(int* a) {
+    swap(a, 1, heapsize);
+    --heapsize;
+    heapify(a, heapsize, 1);
+    return *(a+heapsize+1);
+}
+
+int* heapsort(int* a, int n) {
+    int* b = malloc(sizeof(int) * n);
+    build(a, n);
+    for(unsigned i = 0; i < n; ++i) {
+        b[i] = extract(a);
+;
+    }
+
+    return b;
+}
+
+void increase_key(int* a, int i, int k) {
+    swap(a, i, k);
+    while(i > 1 && compare(a[i>>1], a[i])) {
+        swap(a, i, i >> 1);
+        i >>= 1;
+    }
+}
+
+int main() {
+    heapsize = 6;
+    int* a = malloc(sizeof(int) * 7);
+
+    for(unsigned i = 1; i < 7; ++i)
+        a[i] = i;
+    build(a, 6);
+    for(unsigned i = 1; i <= heapsize; ++i)
+        printf("%d ", *(a+i));
+
+    printf("\n");
+    printf("max value = %d\n", extract(a));
+
+    for(unsigned i = 1; i <= heapsize; ++i)
+        printf("%d ", *(a+i));
+
+    printf("\n");
+    increase_key(a, 1, 4);
+    for(unsigned i = 1; i <= heapsize; ++i)
+        printf("%d ", *(a+i));
+    printf("\n");
+    int n = heapsize;
+    int* b = heapsort(a, heapsize);
+
+    printf("heapsort = ");
+    for(unsigned i = 0; i < n; ++i)
+        printf("%d ", *(b+i));
+    free(b);
+    free(a);
+    return 0;
+}