Supongo que sabes qué es el montón, así que podría omitirlo. Construiré el montón máximo en este ejemplo.
Para construir un montón binario en una matriz, podríamos usar el simple hecho:
- suponga que ha dejado un hijo, que es un montón válido (preservando la propiedad del montón)
- suponga que tiene un hijo correcto, que es un montón válido
- si desea hacer un montón de esos 2 montones secundarios y un nodo principal, simplemente mueva su nodo principal hacia abajo (mediante el intercambio) con el máximo de elementos secundarios a continuación. Esto se llama operación de “hundimiento”, si no recuerdo mal.
Comenzamos simplemente diciendo que nuestros niveles de árbol más bajos (hojas) ya son montones válidos. Luego, para cada elemento “predecesor” lo hundimos para mantener la propiedad del montón.
- ¿Cómo las aplicaciones como el Partometer 3D calculan la longitud en 3D usando la cámara y la entrada táctil?
- ¿Cuáles son los requisitos previos para la introducción del algoritmo antes de tomarlo?
- ¿Qué libro sobre algoritmos es una lectura obligada para un programador?
- Cómo encontrar la cantidad mínima de pasos necesarios para eliminar todos los peones del tablero de ajedrez
- Sistemas distribuidos: ¿Existe un algoritmo de elección de líder para un anillo sincrónico en el que todos los procesadores menos uno tienen la misma ID?
Observación simple: hundirse requiere tanta complejidad como la altura del árbol debajo. Entonces terminas con log2 (N) de capas, donde cada una toma alrededor de i * n / 2 ^ i operaciones. En resumen, te deja con 2 * n límite superior.
Vaya, wiki lo tiene, así que podrías haberlo leído mejor allí: https://en.wikipedia.org/wiki/Bi…
