Saltar a contenido

Ejercicios · Estructuras C26

Heapsort y la cola de prioridad: construir un montículo a partir de un arreglo cualquiera en Θ(n), ordenar con él sin arreglo auxiliar, las funciones de montículo de la STL, el TAD cola de prioridad y el contenedor priority_queue. Cada enlace abre una actividad que se trabaja directo en el navegador, en el orden de los temas de la sesión. Los arreglos y los programas son una ronda nueva sobre el mismo tema. Las más exigentes son ordenar y priority-queue.

Construir un montículo

construir

Por qué se empieza en la casilla n / 2 − 1, la traza de cada llamado a bajar, un arreglo de diez claves para hacer a mano y el peor caso con 1023 claves contra las inserciones una por una.

Heapsort

ordenar

Seis claves ordenadas paso a paso, por qué el máximo va a a[fin], dos rondas a mano, lo que pasa con dos claves iguales y lo que heapsort tiene frente a merge sort y quicksort.

El montículo en la STL

stl-heap

Lo que deja cada llamada de make_heap, push_heap y pop_heap sobre un vector, en qué orden van con push_back y pop_back, cómo se ordena con sort_heap y el montículo de mínimos con greater<int>().

El TAD cola de prioridad

contrato

Lo que devuelve una secuencia de operaciones, qué dice el contrato de extraer de una cola vacía, qué TAD guarda los eventos de un simulador y cómo quedarse con las cinco lecturas más altas de un millón guardando solo cinco.

El contenedor priority_queue

priority-queue

Lo que imprime un programa con push, top y pop, un comparador que deja el menor arriba, llamadas de soporte con la misma prioridad y lo que la cola no deja hacer.