Heapsort
- Fecha
- 1964 · fiabilidad alta
- Lugar
- Borehamwood, Inglaterra, Reino Unido
- Autoría
- J. W. J. Williams
- Ámbito
- Saber y símbolos
Qué es
Williams publicó el algoritmo heapsort, que primero reorganiza un array en un montículo binario —una estructura en la que cada nodo es mayor que sus hijos— y luego extrae repetidamente el máximo para producir una lista ordenada en el sitio y en tiempo n log n. El mismo año, Robert W. Floyd mejoró el método de construcción del montículo.
A qué dio paso
- Algoritmos de ordenación eficientes en el sitio
- Colas de prioridad basadas en montículos
Se apoya en
- Árbol binario
Hizo posible
- Cola de prioridad (heap)