summaryrefslogtreecommitdiff
path: root/2_anno/Algoritmi/data_structures
diff options
context:
space:
mode:
Diffstat (limited to '2_anno/Algoritmi/data_structures')
-rw-r--r--2_anno/Algoritmi/data_structures/heap.c103
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;
+}