Aplicaciones, ventajas y desventajas de Heap

Heap es una estructura de datos especial basada en un árbol donde el tres es siempre un árbol binario completo . Los montones son de dos tipos: Montón máximo y Montón mínimo. En el caso del montón máximo, el Node raíz tendrá un valor más alto que su subárbol, y para el montón mínimo, el Node raíz tendrá un valor más bajo que su subárbol.

Operaciones de montón:

• Heapify : un proceso de creación de un montón a partir de una array.
• Inserción : proceso para insertar un elemento en la complejidad de tiempo de montón existente O (log N).
• Eliminación : eliminar el elemento superior del montón o el elemento de mayor prioridad, y luego organizar el montón y devolver el elemento con complejidad de tiempo O (log N).
• Peek: para verificar o encontrar el elemento más anterior en el montón (elemento máximo o mínimo para el montón máximo y mínimo).

Aplicación de la estructura de datos del montón:

• Heap se utiliza para construir una cola de prioridad.
• Heap sort es uno de los algoritmos de clasificación más rápidos con una complejidad de tiempo de O(N* log(N), y es fácil de implementar.
• Best First Search (BFS) es una búsqueda informada, donde a diferencia de la cola en Breadth-First Search , esta técnica se implementa utilizando una cola de prioridad.

Aplicación en tiempo real de Heap:

• Tratamiento del paciente: en un hospital, se trata primero a un paciente de emergencia o al paciente con más lesiones. Aquí la prioridad es el grado de lesión.
• Los sistemas relacionados con la seguridad utilizan la ordenación en montón, como el kernel de Linux.

Ventajas de la estructura de datos del montón:

• Menos complejidad de tiempo, para insertar o eliminar un elemento en el montón, la complejidad de tiempo es solo O (log N).
• Ayuda a encontrar el número mínimo y el número mayor.
• Para echar un vistazo al elemento más anterior, la complejidad del tiempo es constante O (1).
• Se puede implementar usando una array, no necesita espacio adicional para el puntero .
• Un montón binario es un árbol binario equilibrado y fácil de implementar.
• El montón se puede crear con tiempo O (N).

Desventajas de la estructura de datos del montón:

• La complejidad de tiempo para buscar un elemento en Heap es O(N).
• Para encontrar un sucesor o predecesor de un elemento, el montón toma un tiempo O(N), mientras que BST toma solo un tiempo O(log N).
• Para imprimir todos los elementos del montón en orden ordenado, la complejidad del tiempo es O (N * log N), mientras que, para BST, solo toma O (N) tiempo.
• La gestión de la memoria es más compleja en la memoria del montón porque se usa globalmente. La memoria del montón se divide en dos partes: las generaciones antiguas y la generación joven, etc. en la recolección de basura de Java.