Facebook
From Oscar Cortes Molina, 4 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 149
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. void heapify(int arr[], int n, int i)
  5. {
  6.  
  7.     int largest = i; // INICIALIZAR masgrande COMO RAIZ
  8.  
  9.     int l = 2 * i + 1; // HIJO IZQUIERDO (l)  
  10.  
  11.     int r = 2 * i + 2; // HIJO DERECHO (r)
  12.  
  13.  
  14.  
  15.     //SI EL NODO IZQ ES MAS GRANDE QUE EL PADRE
  16.     if (l < n && arr[l] > arr[largest])
  17.         largest = l;
  18.  
  19.  
  20.  
  21.     // SI EL NODO DERECHO ES MAS GRANDE QUE EL PADRE  
  22.  
  23.     if (r < n && arr[r] > arr[largest])
  24.  
  25.         largest = r;
  26.  
  27.  
  28.  
  29.     //SI EL NODO MAS GRANDE NO ES LA RAIZ
  30.  
  31.     if (largest != i) {
  32.  
  33.         //swap(arr[i], arr[largest]);
  34.         int aux=arr[largest];
  35.         arr[largest]=arr[i];
  36.                 arr[i]=aux;
  37.  
  38.         //FUNCION RECURSIVA HASTA QUE CADA NODO PADRE  SEA MAYOR QUE SUS HIJOS
  39.         heapify(arr, n, largest);
  40.  
  41.     }
  42. }
  43.  
  44.  
  45.  
  46.  
  47. void heapSort(int arr[], int n)
  48. {
  49. int i;
  50.     // CONTRUYENDO EL HEAP(MONTICULO)
  51.  
  52.     for (i = n/2-1;i>=0;i--){
  53.        
  54.  
  55.         heapify(arr, n, i);
  56.     }
  57.     // One by one extract an element from heap (ESTE NO LO ENTIENDO)
  58.     for (i = n - 1; i >= 0; i--) {
  59.  
  60.         // MOVER LA RAIZ ACTUAL AL FINAL
  61.                 int aux2=arr[i];
  62.                  arr[i]=arr[0];
  63.                  arr[0]=aux2;
  64.      
  65.         // VOLVER A LLAMAR A LA FUNCION RESTANDOLE UNO AL TAMA�O DEL HEAP
  66.  
  67.         heapify(arr, i, 0);
  68.  
  69.     }
  70. }
  71.  
  72.  
  73. /*FUNCION PARA IMPRIMIR EL ARREGLO YA ORDENADO */
  74.  
  75.  
  76. void printArray(int arr[], int n)
  77. {
  78. int i;
  79.     for (i = 0; i < n; ++i)
  80.                 printf("%i  ",arr[i]);
  81.      
  82.                 printf("\n");
  83.      
  84. }
  85.  
  86.  
  87.  
  88.  
  89. int main()
  90. {
  91.  
  92.     int arr[] = { 12, 11, 13, 5, 6, 7};
  93.  
  94.     int n = 6,i;
  95.     printf("arreglo original:\n");
  96.     for(i=0;i<n;i++){
  97.         printf("%i  ",arr[i]);
  98.        
  99.         }
  100.         printf("\n\n");
  101.     heapSort(arr, n);
  102.         printf("arreglo ordenado:\n");
  103.     printArray(arr, n);
  104. }