Preguntas Estructura de Datos

1.- Colas de Prioridad admite dos operaciones: eliminar el máximo e insertar ¿Cuáles son los nombres de método que se utiliza para cada tipo?

R:

2.- Un árbol binario está ordenado en montón, si la clave en cada nodo es __________ o __________ que la clave en ese nodo tiene dos hijos (si los hay).

3.- Heapsort se divide en dos fases: 1.- ___________ del montón, donde reorganizamos la matriz original en un montón, y 2.-____________ del montón, donde sacamos los elementos del montón en orden decreciente para generar el resultado ordenado

4.- Se dice que podemos ahorrar tiempo al evitar verificar si el objeto ha alcanzado su posición, simplemente promoviendo al mayor de los dos hijos hasta que se alcance la parte inferior, y luego regresar al montón a la posición correcta. Esta idea reduce el número de comparaciones en un factor de 2 asintóticamente, cerca del número utilizado por mergesort (para una matriz ordenada al azar), ¿Quién observó esto en 1964?

R:

Colas de Prioridad

Muchas aplicaciones requieren que procesemos los elementos que tienen claves en orden, pero no necesariamente en orden completo y no necesariamente todos a la vez. A menudo, recopilamos un conjunto de elementos, luego procesamos el que tiene la clave más grande, luego quizás recopilamos más elementos, luego procesamos el que tiene la clave más grande actual, y así sucesivamente. Por ejemplo, es probable que tenga una computadora (o un teléfono celular) que sea capaz de ejecutar varias aplicaciones al mismo tiempo. Este efecto generalmente se logra asignando una prioridad a los eventos asociados con las aplicaciones, y luego siempre eligiendo procesar el siguiente evento de mayor prioridad. Por ejemplo, es probable que la mayoría de los teléfonos celulares procesen una llamada entrante con mayor prioridad que una aplicación de juego. Un tipo de datos apropiado en tal entorno admite dos operaciones: eliminar el máximo e insertar. Tal tipo de datos se llama una cola de prioridad. Usar colas de prioridad es similar a usar colas (eliminar las más antiguas) y pilas (eliminar las más nuevas), pero implementarlas de manera eficiente es más desafiante. En esta sección, después de una breve discusión de las representaciones elementales donde una o ambas operaciones toman tiempo lineal, consideramos una implementación clásica de la cola de prioridad basada en la estructura de datos del montón binario, donde los elementos se mantienen en una matriz, sujeto a cierto ordenamiento las restricciones que permiten implementaciones eficientes (tiempo logarítmico) eliminan el máximo y lo insertan. Algunas aplicaciones importantes de las colas de prioridad incluyen sistemas de simulación, donde las claves corresponden a los tiempos de eventos, que se procesarán en orden cronológico; programación de tareas, donde las claves corresponden a las prioridades que indican qué tareas se deben realizar primero; y cálculos numéricos, donde las claves representan errores computacionales, indicando en qué orden debemos tratarlos. Consideramos en el Capítulo 6 un estudio de caso detallado que muestra el uso de colas de prioridad en una simulación de colisión de partículas. Podemos usar cualquier cola de prioridad como base para un algoritmo de clasificación insertando una secuencia de elementos, y luego eliminando sucesivamente los más pequeños para eliminarlos, en orden. Un importante algoritmo de clasificación conocido como heapsort también se deriva naturalmente de nuestras implementaciones de cola de prioridad basadas en el montón. Más adelante en este libro, veremos cómo usar las colas de prioridad como bloques de construcción para otros algoritmos. En el Capítulo 4, veremos cómo las colas de prioridad son una abstracción apropiada para implementar varios algoritmos fundamentales de búsqueda de gráficos; En el Capítulo 5, desarrollaremos un algoritmo de compresión de datos utilizando los métodos de esta sección. Estos son solo algunos ejemplos del importante papel que desempeña la cola de prioridad como herramienta en el diseño de algoritmos.

...