Mark CC, informático de Google, cuenta en su blog cómo funciona y se implementa un heap binario. Una herramienta que todo informático debería conocer. Estas estructuras de datos son muy sencillas, pero tremendamente poderosas para ciertas aplicaciones. Por ejemplo, pueden utilizarse para ordenar datos muchísimo mas rápido que quicksort y otros algoritmos similares. La explicación es tan sencilla que se puede entender con poco inglés. Implementación eficiente: http://scienceblogs.com/goodmath/2008/04/implementing_compact_binary_he.php
Supongo que es una estructura de datos que conoce ya todo informático no? Por lo menos yo lo di en 2º de carrera... Pero bueno, nunca está de más recordarla... Eso sí, lo de que sirve para ordenar datos muchísimo más rápido que quicksort... dependerá del caso, no? Como siempre, dependiendo de los datos de entrada, unos algoritmos serán mejores que otros. Si los elementos están ordenados a la inversa, si estás en un dominio discreto (entonces sí se puede decir que hay métodos mucho más eficaces)... los heaps tampoco son la panacea!
Comentarios
Supongo que es una estructura de datos que conoce ya todo informático no? Por lo menos yo lo di en 2º de carrera... Pero bueno, nunca está de más recordarla... Eso sí, lo de que sirve para ordenar datos muchísimo más rápido que quicksort... dependerá del caso, no? Como siempre, dependiendo de los datos de entrada, unos algoritmos serán mejores que otros. Si los elementos están ordenados a la inversa, si estás en un dominio discreto (entonces sí se puede decir que hay métodos mucho más eficaces)... los heaps tampoco son la panacea!