Heap

H
E
A
P
S
O
R
T

## ¿QUE ES HEAPSORT?

Es un método de ordenamiento por selección. Heap: Es un árbol binario de atura mínima, en que los nodos del nivel mas bajo están mas a la izquierda posible. La información es almacenada de manera que al recorrer un camino desde la raíz hacia las hojas, los datos se encuentran en orden descendente.

### Características de heapsort

- Es un árbol binario completo.
- Todos los nodos en el árbol siguen la propiedad de que son mayores que sus hijos, es decir, el elemento más grande está en la raíz y ambos son hijos y más pequeños que la raíz, y así sucesivamente. Tal montón se llama max-heap.
- Si, en cambio, todos los nodos son más pequeños que sus hijos, se llama min-heap.
- Fue el primer algoritmo que surgió de los que ordenan en O(n log n).
- Ordena en el lugar.
- No utiliza memoria auxiliar.
- No es Estable.

  ### VENTAJAS Y DESVENTAJAS DE HEAPSORT

  #### Ventajas

- Funciona efectivamente con datos desordenados.
- Su desempeño es en promedio tan bueno como el Quicksort.
- No utiliza memoria adicional.

  #### Desventajas

- Método complejo.
- No es estable.

  ### TIEMPO DE EJECUCIÓN

  Este método garantiza que el tiempo de ejecución siempre es de:
  O(n log n)
  El Heapsort está basado en el uso de un tipo especial de árbol binario. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en n log n.

  ### ALGORTIMO

  1. Se construye el Heap/montículo a partir del arreglo original.
  2. La raíz se coloca en el arreglo.
  3. El último elemento del montículo se vuelve la raíz.
  4. La nueva raíz se intercambia con el elemento de mayor valor por nivel.
  5. Tras el paso anterior la raíz vuelve a ser el mayor del montículo.
  6. Se repite el paso 2 hasta que quede el arreglo ordenado.

  ### EJEMPLO

  Ordenar el siguiente arreglo de numeros por el metodo HEAPSORT: 16, 14, 10, 8, 7, 9, 3, 2, 4, 1.

  #### SOLUCIÓN

  ## VIDEO COMPLEMENTARIO

  #### Ordenamiento heap sort

  ## REFERENCIAS ELECTRONICAS

- https://estructuras-de-datos.wikispaces.com/Heapsort
- http://ordenamientoheapsort.blogspot.mx/
- https://es.slideshare.net/DanielGmez3/algoritmo-de-ordenamiento-heap-sort
- https://www.programiz.com/dsa/heap-sort
- http://metodopormonticulos.blogspot.mx/
- http://pier.guillen.com.mx/algorithms/03-ordenacion/03.4-heapsort.html
- https://www.ecured.cu/Heapsort
- http://btechsmartclass.com/DS/U3_T7.html
- http://metodopormonticulos.blogspot.mx/