fork(1) 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
comments (?)
stdin 
Standard input is empty
stdout 
0 1 2 3 4 5 6 7 8 9 10
https://ideone.com/1ELXWl
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!