Heap vs Binary Search Tree (BST)

169

¿Cuál es la diferencia entre un montón y BST?

¿Cuándo usar un montón y cuándo usar un BST?

Si desea obtener los elementos de forma ordenada, ¿es mejor BST sobre el montón?

kc3
fuente
13
Esta pregunta parece estar fuera de tema porque se trata de informática y debe hacerse en cs.stackexchange.com
Flujo
3
@Flow se ha preguntado allí en: cs.stackexchange.com/questions/27860/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Siento que se relaciona tanto con el intercambio de pila como con el desbordamiento de pila. Así que tenerlo aquí está bien
Azizbro

Respuestas:

191

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 asintóticamente
  • **: 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: ¿Se usan montones Fibonacci o colas Brodal en la práctica en alguna parte?

  • 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 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. ¿Podemos usar el árbol de búsqueda binario para simular la operación de montón? (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:

Argumento intuitivo:

  • los niveles del árbol inferior tienen exponencialmente más elementos que los niveles superiores, por lo que es casi seguro que los elementos nuevos 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. por ejemplo para Dijkstra. Posible sin costo de tiempo extra.

Punto de 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:

ingrese la descripción de la imagen aquí

  • 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 matriz dinámica. Dado que 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.

  • BST vs análisis detallado de hashmap en: ¿Qué estructura de datos está dentro de std :: map en C ++?

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 tiempos para inserciones individuales.

ingrese la descripción de la imagen aquí

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 las latencias de acceso a la memoria que se realizan 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.

    Con este mayor detalle, sin embargo, también podemos ver 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 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 los montones de punteros: ¿es posible realizar implementaciones eficientes de almacenamiento dinámico binario basado en punteros?

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 + 1struct puntero).

    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 duplicarse. 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 copiar la matriz dinámica de respaldo para duplicar su tamaño requiere O(n) peor de los casos, mientras que el montón de árbol solo realiza 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).

    El nodo superior de un montón es el gran elemento, que solo requiere conocimiento local para mantenerse (conocer a su padre).

Comparando BST vs Heap vs Hashmap:

  • BST: puede ser razonable:

    • conjunto desordenado (una estructura que determina si un elemento se insertó previamente o no). Pero el mapa hash tiende a ser mejor debido a la inserción amortizada O (1).
    • máquina de clasificación Pero montón es generalmente mejor en el que, por lo que heapsort es mucho más ampliamente conocido que la especie de árbol
  • montón: 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 de 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 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 la 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 mapa de hash adicional desde la clave hasta el 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, los 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: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
44
I + 1ed, pero el "papel" que justifica la inserción del montón binario O (1) promedio ahora es un enlace inactivo, y las "diapositivas" simplemente establecen el reclamo sin pruebas. También creo que ayudaría a aclarar que "caso promedio" aquí significa el promedio asumiendo que los valores insertados provienen de una distribución particular , por lo que no estoy seguro de cuán "asesina" es realmente esta característica.
j_random_hacker
3
BST y BST equilibrado parecen usarse de manera intercambiable. Debe quedar claro que la respuesta se refiere a BST equilibrado para evitar confusiones.
gkalpak
2
@Bulat Siento que estamos divagando un poco, pero si queremos tanto max como min al mismo tiempo, podríamos tener problemas para mantener dos montones si no tenemos cuidado - stackoverflow.com/a/1098454/7154924 . Probablemente sea mejor usar un montón máximo-mínimo (debido a Atkinson et al.), Que está específicamente diseñado para este propósito.
flow2k
1
@CiroSantilli 新疆 改造 中心 六四 事件 法轮功: No entiendo por qué la operación de eliminación de un montón binario es O (log n). Esto solo funciona si tiene un puntero al elemento en el montón, pero en la mayoría de los casos de uso, tiene la clave y necesita encontrar primero el elemento que toma O (n).
Ricola
55
la inserción del montón es log (n) no o (1)
Bobo
78

Heap solo garantiza que los elementos en niveles superiores sean mayores (para max-heap) o menores (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.

Código Dante May
fuente
8
"El montón solo garantiza que los elementos en los niveles más altos son mayores (para el montón máximo) o más pequeños (para el montón mínimo) que los elementos en los niveles más bajos, ..." - el montón no aplica esto por nivel , sino solo en padre-hijo- cadenas [1, 5, 9, 7, 15, 10, 11]representa un montón mínimo válido, pero 7en el nivel 3 es más pequeño que 9en el nivel 2. Para una visualización, consulte, por ejemplo, los elementos 25y 19en la imagen de Wikipedia de muestra para los montones . (También tenga en cuenta que las relaciones de desigualdad entre los elementos no son estrictas, ya que los elementos no son necesariamente únicos.)
Daniel Andersson
Perdón por la entrada tardía, pero solo quiero tener claridad. Si se ordena el montón binario, entonces el peor caso para la búsqueda sería iniciar sesión correctamente. Entonces, en ese caso, se ordenan los montones binarios mejor que los árboles de búsqueda binarios (BST rojo-negro). Gracias
Krishna
50

Cuándo usar un montón y cuándo usar un BST

Heap es mejor en findMin / findMax ( O(1)), mientras que BST es bueno en todo find ( O(logN)). La inserción 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.

Las primeras diapositivas de aquí explican las cosas muy claramente.

xysun
fuente
3
Si bien el inserto es logarítmico para ambos en el peor de los casos, el inserto de almacenamiento dinámico promedio toma tiempo constante. (Dado que la mayoría de los elementos existentes se encuentran en la parte inferior, en la mayoría de los casos, un nuevo elemento será suficiente con propagarse por uno o dos niveles, en todo caso.)
johncip
1
@xysun Creo que BST es mejor en findMin & findMax stackoverflow.com/a/27074221/764592
Yeo
2
@Yeo: el montón es mejor para findMin xor findMax. Si necesita ambos , entonces BST es mejor.
Mooing Duck
1
Creo que esto es solo un error común. Un árbol binario se puede modificar fácilmente para encontrar min y max como lo señala Yeo. Esto es en realidad una restricción del montón: el único hallazgo eficiente es min o max. La verdadera ventaja del montón es O (1) inserción promedio como explico: stackoverflow.com/a/29548834/895245
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
1
La respuesta de Ciro Santilli es mucho mejor: stackoverflow.com/a/29548834/2873507
Vic Seedoubleyew
9

Como lo mencionaron otros, Heap puede hacer findMin o findMax en O (1) pero no en la misma estructura de datos. Sin embargo, no estoy de acuerdo con que Heap sea mejor en findMin / findMax. De hecho, con una ligera modificación, el BST puede hacer ambas cosas findMin y findMax en O (1).

En este BST modificado, realiza un seguimiento del nodo mínimo y el nodo máximo cada vez que realiza una operación que potencialmente puede modificar la estructura de datos. Por ejemplo, en la operación de inserción, puede verificar si el valor mínimo es mayor que el valor recién insertado y luego asignar el valor mínimo al nodo recién agregado. La misma técnica se puede aplicar al valor máximo. Por lo tanto, este BST contiene esta información que puede recuperar en O (1). (igual que el montón binario)

En este BST (BST equilibrado), cuando usted pop mino pop max, el siguiente valor mínimo que se asignará es el sucesor del nodo mínimo, mientras que el siguiente valor máximo que se asignará es el predecesor del nodo máximo. Por lo tanto, se realiza en O (1). Sin embargo, necesitamos reequilibrar el árbol, por lo tanto, seguirá ejecutando O (log n). (igual que el montón binario)

Me interesaría escuchar tu opinión en el comentario a continuación. Gracias :)

Actualizar

Referencia cruzada a una pregunta similar ¿Podemos usar el árbol de búsqueda binario para simular la operación de montón? para más discusión sobre la simulación de Heap usando BST.

Yeo
fuente
¿Por qué no estás de acuerdo? ¿te importaría compartir tu pensamiento a continuación?
Yeo
Ciertamente, podría almacenar el valor máximo y / o mínimo de un BST, pero ¿qué sucede si desea reventarlo? Debe buscar el árbol para eliminarlo, luego buscar nuevamente el nuevo máximo / mínimo, los cuales son operaciones O (log n). Ese es el mismo orden que las inserciones y eliminaciones en un montón prioritario, con una constante peor.
Justin
@JustinLardinois Lo siento, me olvido de resaltar esto en mi respuesta. En BST, cuando hace min pop, el siguiente valor min que se asignará es el sucesor del nodo min. y si resalta el valor máximo, el siguiente valor máximo que se asignará es el predecesor del nodo máximo. Por lo tanto, todavía se realiza en O (1).
Yeo
Corrección: para popMino popMaxno es O (1), pero es O (log n) porque tiene que ser un BST equilibrado que debe reequilibrarse en cada operación de eliminación. Por lo tanto, es lo mismo que el montón binario popMino popMaxque ejecuta O (log n)
Yeo
2
Puede obtener el primer min / max, pero obtener kth min / max volvería a la complejidad BST normal.
Caos
3

Un árbol de búsqueda binario usa la definición: que para cada nodo, el nodo a la izquierda tiene un valor menor (clave) y el nodo a la derecha tiene un valor mayor (clave).

Donde, como el montón, ser una implementación de un árbol binario utiliza la siguiente definición:

Si A y B son nodos, donde B es el nodo hijo de A, entonces el valor (clave) de A debe ser mayor o igual que el valor (clave) de B. Es decir, clave (A) ≥ clave (B )

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

Corrí en la misma pregunta hoy para mi examen y acerté. sonreír ... :)

Yevgraf Andreyevich Zhivago
fuente
"montón, siendo una implementación de árbol binario" - solo señalando que un montón es una especie de árbol binario, no una especie de BST
Saad
3

Otro uso de BST sobre Heap; debido a una diferencia importante:

  • Encontrar sucesor y predecesor en un BST llevará tiempo O (h). (O (logn) en BST equilibrado)
  • mientras que en Heap, le tomaría a O (n) tiempo encontrar el sucesor o predecesor de algún elemento.

Uso de BST sobre un montón : Ahora, digamos que usamos una estructura de datos para almacenar el tiempo de aterrizaje de los vuelos. No podemos programar un vuelo para aterrizar si la diferencia en los tiempos de aterrizaje es menor que 'd'. Y suponga que se han programado muchos vuelos para aterrizar en una estructura de datos (BST o Heap).

Ahora, queremos programar otro vuelo que aterrizará en t . Por lo tanto, necesitamos calcular la diferencia de t con su sucesor y predecesor (debería ser> d). Por lo tanto, necesitaremos un BST para esto, que lo hace rápido, es decir, en O (logn) si está equilibrado.

EDITADO:

Ordenar BST toma O (n) tiempo para imprimir elementos en orden ordenado (Recorrido transversal), mientras que Heap puede hacerlo en tiempo O (n log). Heap extrae el elemento min y vuelve a heapificar la matriz, lo que hace que realice la clasificación en tiempo O (n logn).

CÓDIGO error
fuente
1
Si. Es de secuencia sin clasificar a ordenada. O (n) tiempo para el recorrido en orden de un BST, que da una secuencia ordenada. Mientras está en Heaps, extrae el elemento min y luego lo vuelve a heapificar en tiempo O (log n). Por lo tanto, se necesitará O (n logn) para extraer n elementos. Y te dejará con una secuencia ordenada.
CODError
from unsorted to sorted sequence. O(n) time for inorder traversal of a BST, which gives sorted sequence.Bueno, desde la secuencia sin clasificar hasta la BST, no conozco un método basado en la comparación de claves con menos de O (n log), que domina la BST para secuenciar parte. (Mientras que hay una construcción de montón O (n)). Consideraría justo (si no tiene sentido) decir que los montones están cerca de la falta de ordenamiento y los BST ordenados.
barba gris
Lo que estoy tratando de explicar aquí es que si tiene un BST y también un Montón de n elementos => entonces todos los elementos podrían imprimirse en orden de ambas estructuras de datos y BST puede hacerlo en O (n) tiempo (Recorrido transversal ), mientras que Heap tardaría O (n logn) tiempo. No entiendo lo que estás tratando de decir aquí. ¿Cómo se dice BST le dará secuencia ordenada en O (n logn).
CODError 01 de
Creo que también está considerando el tiempo necesario para construir un BST y un montón. Pero supongo que ya lo tiene, que lo ha construido a lo largo del tiempo y ahora desea obtener el resultado ordenado. No entiendo tu punto?
CODError
1
Editado ... Espero que estés satisfecho ahora; p y da un +1 si es correcto.
CODError
1

Insertar todos los n elementos de una matriz a BST toma O (n logn). Se pueden insertar n elementos en una matriz en un montón en O (n) tiempo. Lo que le da al montón una ventaja definitiva

AMR
fuente
0

Heap solo garantiza que los elementos en niveles más altos sean mayores (para max-heap) o más pequeños (para min-heap) que los elementos en niveles más bajos

Me encanta la respuesta anterior y poner mi comentario más específico para mi necesidad y uso. Tenía que obtener la lista de ubicaciones n para encontrar la distancia desde cada ubicación hasta un punto específico, por ejemplo (0,0) y luego devolver las ubicaciones am que tienen una distancia menor. Usé Priority Queue que es Heap. Para encontrar distancias y poner en el montón me llevó n (log (n)) n-ubicaciones log (n) cada inserción. Luego, para obtener m con distancias más cortas, se necesitaron m (log (n)) m-ubicaciones log (n) eliminaciones de amontonamiento.

Si tuviera que hacer esto con BST, me habría llevado n (n) la peor inserción de caso. (Digamos que el primer valor es muy pequeño y todos los demás vienen secuencialmente más y más y el árbol se extiende solo al niño derecho o al niño izquierdo en caso de ser cada vez más pequeño. El mínimo habría tomado O (1) tiempo pero nuevamente tuve que equilibrar. Entonces, por mi situación y todas las respuestas anteriores, lo que obtuve es cuando solo estás después de que los valores en la prioridad mínima o máxima van para el montón.

Sahib Khan
fuente