Implementación de la cola de prioridad usando el montón máximo frente a BST equilibrado

Question

El BST equilibrado y el montón máximo realizan la inserción y la eliminación en archivos O(logn). Sin embargo, encontrar el valor máximo en un montón máximo es O(1)pero esto está O(logn)en BST equilibrado.

Si eliminamos el valor máximo en un montón máximo, se necesita O(logn)porque es una operación de eliminación.

En BST equilibrado, eliminar el elemento máximo = encontrar el valor máximo + eliminar; es igual a logn + logn se reduce a O(logn). Así que incluso borrar el valor máximo en BST balanceado sí lo es O(logn).

He leído una de estas aplicaciones de max heap es una cola de prioridad y su propósito principal es eliminar el valor máximo para cada operación de eliminación de la cola. Si eliminar el elemento máximo es O(logn)tanto para el montón máximo como para el BST equilibrado, tengo las siguientes preguntas

• ¿Cuál es el propósito de un montón máximo en la cola de prioridad solo porque es fácil de implementar en lugar de utilizar BST equilibrado con capacidad de búsqueda completa?

• Dado que no hay un cálculo del factor de equilibrio, ¿el montón máximo se puede llamar árbol binario no equilibrado?

• Cada BST equilibrado se puede usar como una cola de prioridad y cuál también se puede buscar en, O(logn)sin embargo, la búsqueda de montón máxima es O(n)correcta.

Todo el tiempo las complejidades se calculan para el peor de los casos. Cualquier ayuda es muy apreciada.

Answer 1

¿Cuál es el propósito de un montón máximo en la cola de prioridad solo porque es fácil de implementar en lugar de utilizar BST equilibrado con capacidad de búsqueda completa?

Algunas ventajas de un montón son:

• Dada una matriz de entrada sin clasificar, un montón todavía se puede construir en O (n) de tiempo , mientras que una BST necesita O (nlogn) tiempo .

• Si la entrada inicial es una matriz, esa misma matriz puede servir como montón, lo que significa que no se necesita memoria adicional para ella. Aunque uno podría pensar en formas de crear una BST usando los datos en el lugar en la matriz, sería bastante extraño (para tipos primitivos) y daría más sobrecarga de procesamiento. Un BST generalmente se crea desde cero, copiando los datos en los nodos a medida que se crean.

  Dato interesante: una matriz ordenada también es un montón, por lo que si se sabe que la entrada está ordenada, no es necesario hacer nada para construir el montón.

• Un montón se puede almacenar como una matriz sin la necesidad de almacenar referencias cruzadas , mientras que un BST generalmente consta de nodos con referencias izquierda y derecha. Esto tiene al menos dos consecuencias:

  • La memoria utilizada para una BST es aproximadamente 3 veces mayor que la de un montón.
  • Aunque varias operaciones tienen la misma complejidad de tiempo tanto para el montón como para BST, la sobrecarga para adaptar una BST es mucho mayor, por lo que el tiempo real dedicado a estas operaciones es un factor (constante) mayor en el caso de BST.

Dado que no hay un cálculo del factor de equilibrio, ¿el montón máximo se puede llamar árbol binario no equilibrado?

Un montón es, de hecho, un árbol binario completo , por lo que siempre está lo más equilibrado posible: las hojas siempre se colocarán en el último o en el último nivel. Un BST autoequilibrado (como AVL, rojo-negro, ...) no puede superar ese alto nivel de equilibrio, donde a menudo tendrá hojas en tres niveles o incluso más.

Cada BST balanceado se puede usar como una cola de prioridad y que también se puede buscar en O (logn). Sin embargo, la búsqueda de montón máxima es O (n) correcta.

Sí, es cierto. Entonces, si la aplicación necesita la función de búsqueda, entonces un BST es superior.

Answer 2

¿Cuál es el propósito de un montón máximo en la cola de prioridad solo porque es fácil de implementar en lugar de utilizar BST equilibrado con capacidad de búsqueda completa?

No. Max heap encaja mejor, ya que está cuidadosamente instrumentado para devolver el siguiente elemento (respetando la prioridad) lo antes posible, en el tiempo O (1). Eso es lo que desea de la cola de prioridad más simple posible.

Dado que no hay un cálculo del factor de equilibrio, ¿el montón máximo se puede llamar árbol binario no equilibrado?

No. También hay un equilibrio. En pocas palabras, el equilibrio de un montón se realiza mediante operaciones de cambio hacia arriba o hacia abajo (intercambiando elementos que están fuera de servicio).

Cada BST balanceado se puede usar como una cola de prioridad y que también se puede buscar en O (logn). Sin embargo, la búsqueda de montón máxima es O (n) correcta.

¡Si! Además, se podría usar una lista vinculada o una matriz. Será más caro en términos de notación O y mucho más lento en la práctica.