fork(2) download
  1. #include <stdio.h>
  2.  
  3. void criarHeap(int v[], int inicio, int final) {
  4. int aux = v[inicio];
  5. int filho = inicio * 2 + 1;
  6. while (filho <= final) {
  7. // Pai tem 2 filhos? Se sim, qual é o maior?
  8. if (filho < final && filho + 1 < final && v[filho] < v[filho + 1]) {
  9. filho++;
  10. }
  11.  
  12. // Troca o filho com o pai se o filho for maior.
  13. if (aux < v[filho]) {
  14. v[inicio] = v[filho];
  15. inicio = filho;
  16. filho = 2 * inicio + 1;
  17. } else {
  18. filho = final + 1;
  19. }
  20. }
  21. v[inicio] = aux; // Pai troca com filho mais profundo mais a direita.
  22. }
  23.  
  24. void heapSort(int v[], int tam) {
  25. int i;
  26. int aux;
  27. for (i = (tam - 1) / 2; i >= 0; i--) { // Cria o heap.
  28. criarHeap(v, i, tam - 1);
  29. }
  30. for (i = tam - 1; i >= 1; i--) { // Pega o maior elemento e coloca na posição o array.
  31. aux = v[0];
  32. v[0] = v[i];
  33. v[i] = aux;
  34. criarHeap(v, 0, i - 1); // Cria o heap sem o maior elemento anterior.
  35. }
  36. }
  37.  
  38. int main(void) {
  39. int teste[] = {8, 4, 2, 9, 5, 0, 10, 7, 1, 3, 6};
  40. heapSort(teste, 11);
  41. for (int i = 0; i <= 10; i++) {
  42. printf("%i ", teste[i]);
  43. }
  44. return 0;
  45. }
  46.  
Success #stdin #stdout 0s 4564KB
stdin
Standard input is empty
stdout
0 1 2 3 4 5 6 7 8 9 10