summaryrefslogtreecommitdiff
path: root/2_anno/Algoritmi
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-10-23 22:07:24 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-10-23 22:07:24 +0200
commit27f23d04f5997c4ce0f90f39e0d29285fbf5c565 (patch)
tree1e8e6c178168e05aaf578b856e0def0722b234b4 /2_anno/Algoritmi
parent51a7a0cf43c4ed8154202dd3d7182a1f166f5635 (diff)
fix: heapsort must be with max-heap
Diffstat (limited to '2_anno/Algoritmi')
-rw-r--r--2_anno/Algoritmi/data_structures/heap.c39
1 files changed, 10 insertions, 29 deletions
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);