diff options
author | Santo Cariotti <santo@dcariotti.me> | 2021-02-06 19:56:36 +0100 |
---|---|---|
committer | Santo Cariotti <santo@dcariotti.me> | 2021-02-06 19:56:36 +0100 |
commit | d2edbc38cac8da52f58c5cd3da6c0c625fa05736 (patch) | |
tree | a51e9a4e56fc9d4c7c9e37576dceedca3a0c72b4 /Year_2/Algorithms/data_structures/heap.c | |
parent | 98f34040820dc3a964b7be59a698323e8cc6c8a3 (diff) |
conf: rename
Diffstat (limited to 'Year_2/Algorithms/data_structures/heap.c')
-rw-r--r-- | Year_2/Algorithms/data_structures/heap.c | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/Year_2/Algorithms/data_structures/heap.c b/Year_2/Algorithms/data_structures/heap.c new file mode 100644 index 0000000..be7024b --- /dev/null +++ b/Year_2/Algorithms/data_structures/heap.c @@ -0,0 +1,95 @@ +#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 = n-1; i != -1; --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 = 0; + int* a = malloc(sizeof(int) * 7); + + insert(a, 5); + insert(a, 24); + insert(a, 1); + insert(a, 12); + insert(a, 35); + insert(a, -1); + + printf("heap = "); + for(unsigned i = 1; i <= heapsize; ++i) + printf("%d ", *(a+i)); + + int n = heapsize; + int* b = heapsort(a, heapsize); + printf("\nheapsort = "); + for(unsigned i = 0; i < n; ++i) + printf("%d ", *(b+i)); + free(b); + free(a); + return 0; +} |