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
116
117
118
119
120
121
122
123
|
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
void heap (int *values, int h){ //algoritmo para tornar o vetor com a propriedade de heap
/*for(int p=0;p<6;p++){
cout<<values[p]<<endl;
}
cout<<endl;*/
for (int i = 0; i < h; i ++){
if (values[i] < values[(2*i + 1)] || values[i] < values[(2*i + 2)]){ //verificamos se qualquer um dos valores dos filhos é maior do que o pai
if (values[(2*i + 1)] > values[(2*i + 2)]){ //aqui veremos qual dos valores será trocado
int a;
//int a, b;
a = values[(2*i + 1)];
//b = values[i];
values[(2*i +1)] = values[i];
values[i] = a;
//values[(2*i + 1)] = b;
}
if (values[(2*i + 1)] < values[(2*i + 2)]){ //aqui veremos qual dos valores será trocado
int a;
//int a, b;
a = values[(2*i + 2)];
//b = values[i];
values[(2*i +2)] = values[i];
//values[(2*i + 2)] = b;}
values[i] = a;
}
}
}
}
void heapsort (int *values, int i, int* ordenado, int p){
ordenado[(p - i)] = values[0]; //aqui ficara o valor do topo da heap, onde ele sera mantido em ordem decrescente
//cout << values[0] << ".\n"; // mostramos na tela o valor do topo
values[0] = values[(p - i)]; // trocamos o valor do topo pelo valor mais ao fundo
values[(p - i)] = 0; // e finalmente, esvaziamos o valor do fundo
}
int altHeap(long double h){
if (h > 0){
if (h > 2){
h--;
}
}
}
int preencherHeap(int p, int *values, long double h){
long double l = pow (2, h);
while(p < l){
values [p] = 0;
p++;
}
}
int encherHeap(int* values,int p)
{
for (int i = 0; i < p; i++){
cout << "digite o valor inteiro positivo desejado" << endl;
cin >> values[i];
}
}
int main(){
int e = 0;
long double a = 0;
cout << "digite quantos valores vc quer na heap" << endl;
cin >> e;
while((pow (2, a) - 1) < e) {
a++;
}
altHeap (a);
int* valores = new int(e);
int *array = new int(e);
//e--;
/*valores[0] = 40;
valores[1] = 10;
valores[2] = 100;
valores[3] = 90;
valores[4] = 20;
valores[5] = 25;
valores[6] = 0; //esse valor foi colocado para o programa não puxar um valor aleatorio da memória*/
//aqui ficaram os valores ordenados
//int valores[] = { 40, 10, 100, 90, 20, 25 };
//altHeap(e, a);
encherHeap(valores,e);
int u = e;
preencherHeap(u, valores, a);
e--;
for(int n = 0; n <= e; n++){
for(int q = 0; q <= e; q ++){
heap(valores, a);
}
heapsort (valores, n, array, e);
//cout<<"heapsort"<<endl;
}
for(int n = 0; n <= e; n++){
cout << array[n] <<endl; // no final, os valores seram mostrados aqui
}
system("pause");
return 0;
}
|
