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