From 27f23d04f5997c4ce0f90f39e0d29285fbf5c565 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Fri, 23 Oct 2020 22:07:24 +0200 Subject: fix: heapsort must be with max-heap --- 2_anno/Algoritmi/data_structures/heap.c | 39 +++++++++------------------------ 1 file changed, 10 insertions(+), 29 deletions(-) (limited to '2_anno/Algoritmi/data_structures') diff --git a/2_anno/Algoritmi/data_structures/heap.c b/2_anno/Algoritmi/data_structures/heap.c index 6939b0e..be7024b 100644 --- a/2_anno/Algoritmi/data_structures/heap.c +++ b/2_anno/Algoritmi/data_structures/heap.c @@ -54,7 +54,7 @@ int extract(int* a) { int* heapsort(int* a, int n) { int* b = malloc(sizeof(int) * n); build(a, n); - for(unsigned i = 0; i < n; ++i) { + for(unsigned i = n-1; i != -1; --i) { b[i] = extract(a); } @@ -70,42 +70,23 @@ void increase_key(int* a, int i, int k) { } int main() { - heapsize = 6; + heapsize = 0; int* a = malloc(sizeof(int) * 7); - a[1] = 5; - a[2] = 24; - a[3] = 1; - a[4] = 12; - for(unsigned i = 1; i < 7; ++i) - printf("%d ", a[i]); - printf("\n"); - build(a, 4); - for(unsigned i = 1; i < 7; ++i) - printf("%d ", a[i]); - printf("\n\n"); - - 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)); + 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)); - 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 = "); + printf("\nheapsort = "); for(unsigned i = 0; i < n; ++i) printf("%d ", *(b+i)); free(b); -- cgit v1.2.3-18-g5258