¿Cuál ' es la diferencia entre un árbol de búsqueda binario y un montón binario?

Heap solo garantiza que los elementos en niveles superiores son mayores (para max-heap) o más pequeños (para min-heap) que los elementos en niveles inferiores, mientras que BST garantiza el orden (de «izquierda» a «derecha») . Si quieres elementos ordenados, elige BST. de Dante no es un geek

Heap es mejor en findMin / findMax (O ( 1)), mientras que BST es bueno en todos los hallazgos (O (logN)). Insertar es O (logN) para ambas estructuras. Si solo le importa findMin / findMax (por ejemplo, relacionado con la prioridad), vaya con heap. Si lo desea todo ordenado, vaya con BST.

por xysun

Comentarios

• Creo que BST es mejor en findMin & findMax stackoverflow .com / a / 27074221/764592
• Creo que esto es solo una comunicación en concepto erróneo. Un árbol binario se puede modificar fácilmente para encontrar el mínimo y el máximo como señala Yeo. Esto es en realidad una restricción del montón: la única búsqueda eficiente es mínima o máxima. La verdadera ventaja del montón es O (1) inserción promedio como explico: stackoverflow.com/a/29548834/895245
• De acuerdo con este video , puede tener valores más grandes en un nivel más bajo, siempre que el más grande no sea descendiente del más bajo.
• El montón se ordena de raíz a hoja y BST se ordena de izquierda a derecha.
• ¿Qué sucede si quiero encontrar la mediana en tiempo constante y eliminar la mediana en tiempo logarítmico? ¿Qué estructura de datos debería elegir? ¿Funcionará la implementación de MinHeap? por favor sugiera.

Resumen

 Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) 

Todos los tiempos promedio en esta tabla son los mismos que los peores, excepto para Insertar.

• *: en todas partes en esta respuesta, BST == BST equilibrado, ya que el desequilibrado es asintótico
• **: usando una modificación trivial explicada en esta respuesta
• ***: log(n) para el montón del árbol de punteros, n para el montón de matriz dinámica

Ventajas del montón binario sobre un BST

• El tiempo promedio de inserción en un montón binario es O(1), para BST es O(log(n)). Este es la característica principal de los montones.

  También hay otros montones que alcanzan O(1) amortizado (más fuerte) como el Fibonacci Heap , e incluso en el peor de los casos, como el cola Brodal , aunque pueden no ser prácticos debido a un rendimiento no asintótico: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• Los montones binarios se pueden implementar de manera eficiente sobre matrices dinámicas o árboles basados en punteros, solo BST árboles basados en punteros. Entonces, para el montón, podemos elegir la implementación de matriz más eficiente en el espacio, si podemos permitirnos latencias de cambio de tamaño ocasionales.

• Creación de montón binario es O(n) peor de los casos , O(n log(n)) para BST.

La ventaja de BST sobre el montón binario

• la búsqueda de elementos arbitrarios es O(log(n)). Esta es la característica principal de las BST.

  Para el montón, es O(n) en general, excepto por el elemento más grande que es O(1).

Ventaja «falsa» del montón sobre BST

• El montón es O(1) para encontrar el máximo, BST O(log(n)).

  Este es un error común, porque es trivial modificar un BST para realizar un seguimiento del elemento más grande y actualizarlo cada vez que ese elemento pueda cambiarse: al insertar un intercambio más grande, al eliminarlo, busque el segundo más grande. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (mencionado por Yeo ).

  En realidad, esta es una limitación de montones en comparación con las BST: la única búsqueda eficiente es la del elemento más grande.

La inserción de pila binaria promedio es O(1)

Fuentes:

• Documento: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Diapositivas de WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argumento intuitivo:

• Los niveles inferiores del árbol tienen exponencialmente más elementos que los niveles superiores, por lo que es casi seguro que los nuevos elementos vayan al final
• inserción de montón comienza desde abajo , BST debe comenzar desde arriba

En un montón binario, aumentar el valor en un índice dado también es O(1) por la misma razón. Pero si desea hacer eso, es probable que desee mantener un índice adicional actualizado sobre las operaciones del montón https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu p. ej. para Dijkstra. Es posible sin costo adicional de tiempo.

GCC C ++ inserto de referencia de la biblioteca estándar en hardware real

Hice una evaluación comparativa de C ++ std::set ( BST de árbol rojo-negro ) y std::priority_queue ( pila de matriz dinámica ) inserte para ver si tenía razón sobre los tiempos de inserción, y esto es lo que obtuve:

• código de referencia
• secuencia de comandos de trazado
• trazar datos
• probado en Ubuntu 19.04, GCC 8.3.0 en una computadora portátil Lenovo ThinkPad P51 con CPU: CPU Intel Core i7-7820HQ (4 núcleos / 8 subprocesos , 2,90 GHz base, 8 MB de caché), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3.000 MB / s)

Así que claramente:

• heap insert t ime es básicamente constante.

  Podemos ver claramente los puntos de cambio de tamaño de la matriz dinámica. Dado que estamos promediando cada 10k inserciones para poder ver cualquier cosa por encima del ruido del sistema , esos picos son de hecho aproximadamente 10k veces más grandes de lo que se muestra.

  El gráfico ampliado excluye esencialmente solo los puntos de cambio de tamaño de la matriz y muestra que casi todas las inserciones caen por debajo de los 25 nanosegundos.

• BST es logarítmico. Todas las inserciones son mucho más lentas que la inserción de pila promedio.

• Análisis detallado de BST vs hashmap en: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ inserta un punto de referencia de la biblioteca estándar en gem5

gem5 es un simulador de sistema completo y, por lo tanto, proporciona un reloj infinitamente preciso con m5 dumpstats. Así que intenté usarlo para estimar tiempos para inserciones individuales.

Interpretación:

• el montón sigue siendo constante, pero ahora vemos con más detalle que hay algunas líneas, y cada línea superior es más dispersa .

  Esto debe corresponder a las latencias de acceso a la memoria que se realizan para inserciones cada vez más altas.

• TODO No puedo interpretar la BST completamente como no parece tan logarítmico y algo más constante.

  Sin embargo, con este mayor detalle, podemos ver también algunas líneas distintas, pero no estoy seguro de lo que representan: esperaría que el resultado final ser más delgado, ya que insertamos la parte superior inferior?

Comparado con esta configuración de Buildroot en un HPI CPU .

BST no se puede implementar de manera eficiente en una matriz

Montón Las operaciones solo necesitan subir o bajar una sola rama de árbol, por lo que O(log(n)) cambios en el peor de los casos, O(1) promedio.

Mantener un BST equilibrado requiere rotaciones de árboles, que pueden cambiar el elemento superior por otro, y requeriría mover toda la matriz (O(n)).

Los montones se pueden implementar de manera eficiente en una matriz

Los índices principales y secundarios se pueden calcular a partir del índice actual como se muestra aquí .

No hay operaciones de equilibrio como BST.

Eliminar min es la operación más preocupante ya que tiene que ser de arriba hacia abajo. Pero siempre se puede hacer «filtrando» una sola rama del montón como se explica aquí . Esto conduce a un O (log (n)) en el peor de los casos, ya que el montón siempre está bien equilibrado.

Si inserta un solo nodo por cada uno que elimina, pierde la ventaja del asintótico O (1) inserto promedio que proporcionan los montones ya que dominaría la eliminación, y también podría usar un BST. Sin embargo, Dijkstra actualiza los nodos varias veces para cada eliminación, por lo que estamos bien.

Montones de matrices dinámicas frente a montones de árboles de punteros

Los montones se pueden implementar de manera eficiente en la parte superior de los montones de punteros: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

La implementación de matriz dinámica es más eficiente en cuanto al espacio. Suponga que cada elemento del montón contiene solo un puntero a un struct:

• la implementación del árbol debe almacenar tres punteros para cada elemento: padre, niño izquierdo y niño derecho. Por lo tanto, el uso de la memoria es siempre 4n (3 punteros de árbol + 1 puntero struct).

  Los BST de árbol también lo harían necesita más información de equilibrio, p. ej. black-red-ness.

• La implementación de la matriz dinámica puede tener el tamaño 2n justo después de una duplicación. Entonces, en promedio, será 1.5n.

Por otro lado, el montón de árbol tiene una mejor inserción en el peor de los casos, porque copiar la matriz dinámica de respaldo para duplicar su tamaño toma O(n) el peor de los casos, mientras que el montón del árbol solo hace nuevas asignaciones pequeñas para cada nodo.

Aún así, el respaldo la duplicación de matrices está O(1) amortizada, por lo que se reduce a una consideración de latencia máxima. Se menciona aquí .

Filosofía

• Las BST mantienen una propiedad global entre un padre y todos los descendientes (izquierda más pequeña, derecha más grande).

  El nodo superior de una BST es el elemento del medio , que requiere un conocimiento global para mantener (saber cuántos elementos más pequeños y más grandes hay).

  Esta propiedad global es más cara de mantener (log n insert), pero ofrece búsquedas más potentes (log n search) .

• Los montones mantienen una propiedad local entre el padre y los hijos directos (padre> hijos).

  La nota superior de un montón es el elemento grande, que solo requiere conocimiento local para mantenerse (conocer a sus padres).

Comparando BST vs Heap vs Hashmap:

• BST: puede ser razonable:

  • conjunto desordenado (una estructura que determina si un elemento fue insertado previamente o no). Pero hashmap tiende a ser mejor debido a la inserción amortizada O (1).
  • máquina de clasificación. Pero el montón es generalmente mejor en eso, por lo que heapsort es mucho más conocido que árbol ordenado

• heap: es solo una máquina de clasificación. No puede ser un conjunto desordenado eficiente, porque solo puede verificar rápidamente el elemento más pequeño / más grande.

• mapa hash: solo puede ser un conjunto desordenado, no una máquina de clasificación eficiente, porque el hash mezcla cualquier orden.

Lista doblemente enlazada

Una lista doblemente enlazada puede verse como un subconjunto del montón donde el primer elemento tiene la mayor prioridad, así que comparémoslos aquí también:

• inserción:
  • posición:
    • lista doblemente enlazada: el elemento insertado debe ser el primero o el último, ya que solo tenemos punteros a esos elementos.
    • montón binario: el elemento insertado puede terminar en cualquier posición. Menos restrictivo que la lista enlazada.
  • tiempo:
    • lista doblemente enlazada: O(1) en el peor de los casos, ya que tenemos punteros a los elementos, y la actualización es realmente simple
    • montón binario: O(1) promedio, por lo tanto, peor que la lista vinculada. tener una posición de inserción más general.
• buscar: O(n) para ambos

Un caso de uso para esto es cuando la clave del montón es la marca de tiempo actual: en ese caso, las nuevas entradas siempre irán al principio de la lista. Así que incluso podemos olvidar la marca de tiempo exacta y mantener la posición en la lista como prioridad.

Esto se puede usar para implementar una caché LRU . Al igual que para aplicaciones de montón como Dijkstra , querrá mantener un mapa de hash adicional de la clave al nodo correspondiente de la lista, para encontrar qué nodo actualizar rápidamente .

Comparación de diferentes BST equilibradas

Aunque la inserción asintótica y la búsqueda Los tiempos para todas las estructuras de datos que comúnmente se clasifican como «BST balanceadas» que he visto hasta ahora son iguales, diferentes BBST tienen diferentes compensaciones. Aún no lo he estudiado completamente, pero sería bueno resumir estas compensaciones aquí:

• Árbol rojo-negro . Parece ser el BBST más utilizado a partir de 2019, p. Ej. es el que utiliza la implementación de GCC 8.3.0 C ++
• árbol AVL . Parece ser un poco más equilibrado que BST, por lo que podría ser mejor para la latencia de búsqueda, a costa de hallazgos un poco más costosos.Wiki resume: «Los árboles AVL a menudo se comparan con árboles rojo-negro porque ambos admiten el mismo conjunto de operaciones y toman [el mismo] tiempo para las operaciones básicas. Para aplicaciones de búsqueda intensiva, los árboles AVL son más rápidos que los árboles rojo-negro porque Están más estrictamente equilibrados. Al igual que los árboles rojo-negro, los árboles AVL tienen un equilibrio de altura. En general, ninguno de los dos está equilibrado en peso ni en mu para cualquier mu < 1 / 2; es decir, los nodos hermanos pueden tener números de descendientes muy diferentes. «
• WAVL . El artículo original menciona las ventajas de esa versión en términos de límites en las operaciones de reequilibrio y rotación.

Consulte también

Pregunta similar en CS: What ' s la diferencia entre un árbol de búsqueda binario y un montón binario?

Comentarios

• Excelente respuesta . La aplicación común del montón son median, k min, top k elementos. Para estas operaciones más comunes, elimine min y luego inserte (generalmente tenemos un montón pequeño con pocas operaciones de inserción pura). En la práctica, parece que para estos algoritmos no supera a BST.
• ¡¡¡Respuesta excepcional !!! Al usar deque como estructura de montón subyacente, puede reducir drásticamente los tiempos de cambio de tamaño, aunque sigue siendo O (n) el peor de los casos, ya que necesita reasignar una matriz (más pequeña) de punteros a fragmentos.

Ambos árboles de búsqueda binaria y binary montones son estructuras de datos basadas en árboles.

Los montones requieren que los nodos tengan prioridad sobre sus hijos. En un montón máximo, los elementos secundarios de cada nodo deben ser menores que él mismo. Esto es lo contrario para un montón mínimo:

Los árboles de búsqueda binaria (BST) siguen un orden específico (preorden, en orden, posorden) entre los nodos hermanos. El árbol debe debe ordenarse, a diferencia de los montones:

BST tiene un promedio de $ O (\ log n) $ para inserción, eliminación y búsqueda.
Los montones binarios tienen un promedio $ O (1) $ para findMin / findMax y $ O (\ log n) $ para inserción y eliminación.

Comentarios

• @FrankW La extracción es $ O (\ log n) $, ¿no?

Con la estructura de datos uno tiene que distinguir los niveles de preocupación.

1. Las estructuras de datos abstractas (objetos almacenados, sus operaciones) en este q Las preguntas son diferentes. Uno implementa una cola de prioridad, el otro un conjunto. Una cola de prioridad no está interesada en encontrar un elemento arbitrario, solo el que tiene la mayor prioridad.

2. La implementación concreta de las estructuras. Aquí, a primera vista, ambos son árboles (binarios), aunque con diferentes propiedades estructurales. Tanto el orden relativo de las claves como las posibles estructuras globales difieren. (Algo impreciso, en un BST las claves están ordenadas de izquierda a derecha, en un montón están ordenadas de arriba hacia abajo). Como IPlant comenta correctamente, un montón también debe estar «completo» .

3. Existe una diferencia final en la implementación de bajo nivel . Un árbol de búsqueda binario (no balanceado) tiene una implementación estándar que usa punteros. Un montón binario por el contrario tiene una implementación eficiente usando una matriz (precisamente debido a la estructura restringida).

Además de las respuestas anteriores, el montón debe tener la propiedad de estructura del montón ; el árbol debe estar lleno, y la capa más inferior, que no siempre puede estar llena, debe llenarse de izquierda a derecha sin espacios.