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

Estos dos parecen muy similares y tienen una estructura casi idéntica. ¿Cual es la diferencia? ¿Cuáles son las complejidades de tiempo para las diferentes operaciones de cada uno?

Heap solo garantiza que los elementos en niveles superiores sean 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 desea elementos ordenados, vaya con BST. por 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 quieres todo ordenado, ve con BST.

por xysun

Tanto los árboles de búsqueda binarios como los montones binarios 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 hijos de cada nodo deben ser menores que él. Esto es lo contrario para un montón mínimo:

Los árboles de búsqueda binaria (BST) siguen un orden específico (preordenar, ordenar, posordenar) entre los nodos hermanos. El árbol debe estar ordenado, a diferencia de los montones:

$O(\log n)$
$O(1)$$O(\log n)$

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 Insertar.

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

Ventajas del montón binario sobre un BST

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

  También hay otros montones que alcanzan O(1)amortizados (más fuertes) como el montón de Fibonacci , e incluso el peor de los casos, como la cola Brodal , aunque pueden no ser prácticos debido al 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, BST solo árboles basados ​​en punteros. Entonces, para el montón, podemos elegir la implementación de matriz más eficiente en cuanto al espacio, si podemos permitir latencias de cambio de tamaño ocasionales.

• La creación de almacenamiento dinámico binario es el O(n)peor de los casos , O(n log(n))para BST.

Ventaja de BST sobre el montón binario

• buscar elementos arbitrarios es O(log(n)). Esta es la característica asesina de los 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)encontrar max, BST O(log(n)).

  Esta es una idea errónea común, porque es trivial modificar un BST para realizar un seguimiento del elemento más grande y actualizarlo cada vez que se pueda cambiar ese elemento: al insertar un intercambio más grande, al quitar, encontrar 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 los montones en comparación con los BST: la única búsqueda eficiente es la del elemento más grande.

La inserción del montón binario promedio es O(1)

Fuentes:

• Papel: 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 del árbol inferior tienen exponencialmente más elementos que los niveles superiores, por lo que es casi seguro que los nuevos elementos irán al final
• la inserción del 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 de almacenamiento dinámico https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease- key-operation-for-min-heap-based-prioridades-queu, por ejemplo, para Dijkstra. Posible sin costo de tiempo extra.

Referencia de inserción de biblioteca estándar GCC C ++ en hardware real

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

• código de referencia
• guión de la trama
• datos de la trama
• 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 hilos, base de 2.90 GHz, 8 MB de caché), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3,000 MB / s)

Tan claro:

• El tiempo de inserción del montón es básicamente constante.

  Podemos ver claramente los puntos de cambio de tamaño de la matriz dinámica. Como estamos promediando cada 10k insertos 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 25 nanosegundos.

• BST es logarítmico. Todos los insertos son mucho más lentos que el inserto de almacenamiento dinámico promedio.

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

Prueba patrón de inserción de biblioteca estándar GCC C ++ en gem5

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

Interpretación:

• el almacenamiento dinámico sigue siendo constante, pero ahora vemos con más detalle que hay algunas líneas y que cada línea superior es más escasa.

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

• TODO Realmente no puedo interpretar el BST completamente, ya que no se ve 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 la línea inferior sea más delgada, ya que insertamos la parte superior inferior.

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

BST no se puede implementar de manera eficiente en una matriz

Las operaciones de almacenamiento dinámico solo necesitan subir o bajar una sola rama de árbol, por lo que, en el O(log(n))peor de los casos, los intercambios son O(1)promedio.

Mantener un BST equilibrado requiere rotaciones de árbol, lo que puede 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.

Delete 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 peor caso de O (log (n)), ya que el montón siempre está bien equilibrado.

Si está insertando un solo nodo por cada uno que elimine, entonces pierde la ventaja del inserto promedio asintótico O (1) que los montones proporcionan como la eliminación dominaría, 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 matriz dinámica vs montones de árbol de puntero

Los montones se pueden implementar de manera eficiente sobre 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 espacio. Supongamos que cada elemento del montón contiene solo un puntero a struct:

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

  Los BST de árbol también necesitarían más información de equilibrio, por ejemplo, negro-rojo-ness.

• La implementación de matriz dinámica puede ser de tamaño 2njusto después de una duplicación. Entonces, en promedio, va a ser 1.5n.

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

Aún así, la matriz de respaldo que se duplica se O(1)amortiza, por lo que se reduce a una consideración de latencia máxima. Mencionado aquí .

Filosofía

• Los 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 un BST es el elemento 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 costosa de mantener (log n insert), pero proporciona búsquedas más potentes (log n search).

• Los montones mantienen una propiedad local entre padre e hijos directos (padre> hijos).

  La nota más alta de un montón es el gran elemento, que solo requiere conocimiento local para mantener (conocer a tus padres).

Lista doblemente enlazada

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

• inserción:
  • posición:
    • lista doblemente vinculada: 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 vinculada.
  • hora:
    • lista doblemente vinculada: el O(1)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. Compensación por tener una posición de inserción más general.
• búsqueda: 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. Por lo tanto, incluso podemos olvidar la marca de tiempo exacta por completo, y simplemente mantener la posición en la lista como prioridad.

Esto se puede usar para implementar un caché LRU . Al igual que para las aplicaciones de almacenamiento dinámico como Dijkstra , querrá mantener un hashmap adicional de la clave al nodo correspondiente de la lista, para encontrar qué nodo actualizar rápidamente.

Comparación de diferentes BST equilibrados

Aunque la inserción asintótica y los tiempos de búsqueda para todas las estructuras de datos que comúnmente se clasifican como "BST equilibrados" que he visto hasta ahora es la misma, diferentes BBST tienen diferentes compensaciones. Todavía no he estudiado completamente esto, pero sería bueno resumir estas compensaciones aquí:

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

Ver también

Pregunta similar sobre CS: ¿Cuál es la diferencia entre un árbol de búsqueda binario y un montón binario?

Con la estructura de datos, hay que distinguir los niveles de preocupación.

1. Las estructuras de datos abstractos (objetos almacenados, sus operaciones) en esta pregunta son diferentes. Uno implementa una cola prioritaria, el otro un conjunto. Una cola prioritaria no está interesada en encontrar un elemento arbitrario, solo el que tiene 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 teclas como las posibles estructuras globales difieren. (Algo impreciso, en una BSTclave se ordena de izquierda a derecha, en un montón se ordena de arriba hacia abajo). Como IPlant comenta correctamente, un montón también debe estar "completo".

3. Hay 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 utiliza punteros. Un montón binario, por el contrario, tiene una implementación eficiente utilizando una matriz (precisamente por la estructura restringida).

Además de las respuestas anteriores, el montón debe tener la propiedad de estructura de 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.