-
Notifications
You must be signed in to change notification settings - Fork 0
/
heapsort.c
115 lines (92 loc) · 2.24 KB
/
heapsort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdlib.h>
#include <stdio.h>
typedef struct heap Heap;
struct heap {
int n;
int max_n;
int *vet;
};
void cria_heap (Heap *heap, int max_n) {
heap->n = 0;
heap->n = max_n;
heap->vet = (int *) calloc (sizeof(int), max_n);
}
void destroi_heap(Heap *heap) {
heap->n = 0;
free (heap->vet);
}
int pai(int i) { return (i - 1) / 2; }
int filho_esq (int i) { return 2 * i + 1; }
int filho_dir (int i) { return 2 * i + 2; }
int existe_pai(int i) { return i > 0; }
int existe_filho_esq (int i, int n) { return (2 * i + 1) < n; }
int existe_filho_dir (int i, int n) { return (2 * i + 2) < n; }
void insere(Heap *heap, int elem) {
if (heap->n + 1 == heap->max_n) {
printf("Heap lotado! \n");
exit(-1);
}
else {
int i = heap->n;
while (existe_pai(i) && heap->vet[pai(i)] < elem) {
heap->vet[i] = heap->vet[pai(i)];
i = pai(i);
}
heap->vet[i] = elem;
heap->n++;
}
}
void desce_raiz(Heap* heap, int pos_raiz) {
int raiz = heap->vet[pos_raiz];
int i = pos_raiz;
while ((existe_filho_esq(i, heap->n) && raiz < heap->vet[filho_esq(i)]) ||
(existe_filho_dir(i, heap->n) &&
raiz < heap->vet[filho_dir(i)])) {
int j = filho_esq(i);
if (existe_filho_dir(i, heap->n) &&
heap->vet[filho_dir(i)] > heap->vet[filho_esq(i)])
j = filho_dir(i);
heap->vet[i] = heap->vet[j];
i = j;
}
heap->vet[i] = raiz;
}
int remove_max(Heap* heap) {
if (heap->n == 0) {
printf("Heap lotado! \n");
exit(-1);
}
else {
int elem = heap->vet[0];
heap->n--;
heap->vet[0] = heap->vet[heap->n];
desce_raiz(heap, 0);
return elem;
}
}
void monta_heap(Heap* heap, int* vet, int n) {
int i;
heap->n = n;
heap->max_n = n;
heap->vet = vet;
for (i = n / 2; i >= 0; i--)
desce_raiz(heap, i);
}
int vazio(Heap* heap) {
return heap->n == 0;
}
void exibe_vetor(int vet[], int n_elem) {
int i;
for (i =0; i < n_elem; i++)
printf("%d ", vet[i]);
printf("\n");
}
void heapsort(int *vet, int n) {
Heap heap;
int i;
monta_heap(&heap, vet, n);
for (i = 0; i < n; i++) {
int aux = remove_max(&heap);
vet[heap.n] = aux;
}
}