algorithm - min heap c++

Heap vs Binary Search Tree(BST) (8)

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 todos los hallazgos ( O(logN) ). Insertar es O(logN) para ambas estructuras. Si solo te importa findMin / findMax (por ejemplo, relacionado con la prioridad), ve con Heap. Si quieres que todo esté ordenado, ve con BST.

Las primeras diapositivas de here explican las cosas muy claramente.

¿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, ¿BST es mejor que Heap?

Heap simplemente garantiza que los elementos en niveles más altos son mayores (para max-heap) o más pequeños (para min-heap) que los elementos en niveles inferiores

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

Si tuviera que hacer esto con BST, me hubiera llevado n (n) la peor inserción de casos. (Digamos que el primer valor es muy pequeño y el resto viene de forma secuencial más larga y más larga y el árbol se extiende a la derecha o solo a la izquierda en el caso de más pequeño y más pequeño. El min hubiera tardado O (1) vez, pero nuevamente tuve que equilibrar. Por lo tanto, desde mi situación y todas las respuestas anteriores, lo que obtuve es cuando solo se buscan los valores mínimos o máximos. para el montón.

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

En esta BST modificada, realiza un seguimiento del nodo mínimo y del nodo máximo cada vez que realiza una operación que puede modificar potencialmente 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, luego asigne 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). (lo mismo que el montón binario)

En esta BST (BST balanceada), cuando pop min o 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 max. Por lo tanto, se realiza en O (1). Sin embargo, tenemos que volver a equilibrar el árbol, por lo que todavía se ejecutará O (log n). (lo mismo 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 pila? para más discusión sobre la simulación de Heap usando BST.

Heap solo garantiza que los elementos en niveles más altos 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, ve con BST.

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

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

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

Uso de BST sobre un Heap : 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 a ''d''. Y supongamos que muchos vuelos han sido programados para aterrizar en una estructura de datos (BST o Heap).

Ahora, queremos programar otro vuelo que aterrice 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:

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

Un árbol de búsqueda binario utiliza 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, al ser una implementación de un árbol binario utiliza la siguiente definición:

Si A y B son nodos, donde B es el nodo secundario 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

Presenté la misma pregunta hoy para mi examen y lo hice bien. sonreír ... :)

Resumen

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

* : en todas partes en esta respuesta, BST == BST balanceado, ya que desequilibrado es asintótico
** : usando una modificación trivial explicada en esta respuesta

Ventajas del montón binario sobre un BST

la inserción promedio de tiempo en un montón binario es O(1) , para BST es O(log(n)) . Esta es la característica principal de montones.
También hay otros montones que alcanzan O(1) amortizado (más fuerte) como el Fibonacci Heap , e incluso el peor de los casos, como la cola de Brodal , aunque pueden no ser prácticos debido a un rendimiento no asintótico: ¿Se usan montones de Fibonacci o Brodal? en la práctica en cualquier lugar?
Los montones binarios pueden implementarse eficientemente sobre las matrices, BST no puede.
Por lo tanto, no es necesario almacenar 3 punteros por nodo (izquierda, derecha, principal) más datos de equilibrio (p. Ej. RB-ness), lo que permite ahorrar memoria por un factor constante.
la creación del montón binario es O(n) peor caso , O(n log(n)) para BST.

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 BST.
Para el montón, es O(n) en general, a excepción del elemento más grande que es O(1) .

Ventaja "Falsa" de Heap sobre BST

el montón es O(1) para encontrar max, BST O(log(n)) .
Este es un concepto erróneo común, porque es trivial modificar un BST para realizar un seguimiento del elemento más grande y actualizarlo cada vez que ese elemento se puede cambiar: al insertar un intercambio más grande, al quitarlo, 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 montones en comparación con BST: la única búsqueda eficiente es la del elemento más grande.

La inserción media del montón binario 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 inferiores de los árboles tienen exponencialmente más elementos que los niveles superiores, por lo que es casi seguro que los nuevos elementos se ubiquen en la parte inferior
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 el mismo motivo. Pero si desea hacerlo, es probable que desee mantener un índice adicional actualizado en las operaciones de montón. ¿Cómo implementar la operación de disminución de O (logn) para la cola de prioridad basada en min-heap? por ejemplo, para Dijikstra. Posible sin costo adicional de tiempo.

BST no se puede implementar de manera eficiente en una matriz

Las operaciones de montón solo necesitan subir o bajar una única rama de árbol, por lo que O(log(n)) peor de los casos cambia, O(1) promedio.

Mantener un BST balanceado requiere rotaciones de árbol, que pueden cambiar el elemento superior por otro, y requeriría mover todo el conjunto ( O(n) ).

Filosofía

BST mantienen una propiedad global entre un padre y todos los descendientes (se deja más pequeño, el más grande).
El nodo superior de un BST es el elemento medio, que requiere conocimiento global para mantenerse (sabiendo 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 ofrece búsquedas más potentes (log n search).
Los montones mantienen una propiedad local entre los padres y los hijos directos (padres> hijos).
La nota más importante de un montón es el elemento principal, que solo requiere conocimiento local para mantener (conocer a su padre).

Lista doblemente enlazada

Una lista doblemente enlazada se puede ver como un subconjunto del montón donde el primer elemento tiene la mayor prioridad, así que vamos a compararlos 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 el montón.
- hora:
  - lista doblemente enlazada: O(1) peor caso tenemos punteros a los ítems, y la actualización es realmente simple
  - montón binario: O(1) promedio, por lo tanto, peor. 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. Así que incluso podemos olvidar la marca de tiempo exacta por completo, y solo mantener el puesto 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 desde la clave hasta el nodo correspondiente de la lista, para encontrar qué nodo actualizar rápidamente.

Ver también