Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

montón

Montón y cola de prioridad:

La cola de prioridad es un tipo de datos abstracto y el montón es una estructura de datos, por lo que el montón no es una cola de prioridad. El montón es una forma de implementar una cola de prioridad.
Hay muchas formas de implementar colas prioritarias, como matrices y listas vinculadas. Sin embargo, estas implementaciones solo pueden garantizar que una de las operaciones de inserción y eliminación se pueda completar en una complejidad de tiempo O (1) O (1), mientras que la otra operación debe completarse en O (N) O (N) Completada dentro del complejidad del tiempo. El montón puede permitir que la operación de inserción de la cola de prioridad se complete dentro de la complejidad temporal de O (log N) O (logN) y la operación de eliminación se complete dentro de la complejidad temporal de O (log N) O (logN). .

Un montón es un árbol binario especial que cumple las siguientes condiciones:

1. Árbol binario completo (los nodos se colocan en orden de izquierda a derecha);
2. El valor de cada nodo debe ser mayor o igual o menor o igual al valor de su nodo hijo.

Características del montón:

1. Los elementos se pueden insertar en el montón con una complejidad de tiempo O (logN);
2. Los elementos se pueden eliminar del montón con una complejidad de tiempo O (logN);
3. El valor máximo o mínimo en el montón se puede obtener dentro de una complejidad de tiempo O (1).

Clasificación de montones:

Montón máximo: el valor de cada nodo en el montón es mayor o igual que el valor de su nodo secundario. El elemento superior (nodo raíz) del montón máximo es el valor máximo del montón.
Montón mínimo: el valor de cada nodo en el montón es menor o igual que el valor de su nodo secundario. El elemento superior (nodo raíz) de un montón mínimo es el valor mínimo del montón.
El número de nodo actual es i, el número del hijo izquierdo es 2i y el número del hijo derecho es 2i+1.

complejidad del tiempo y complejidad del espacio

clasificación de montón

Teoría: la clasificación del montón se refiere al uso de la estructura de datos del montón para ordenar un conjunto de elementos desordenados.

Los pasos del algoritmo de clasificación de montón mínimo son los siguientes:

Apila todos los elementos en un montón mínimo;
Saque y elimine el elemento superior del montón y coloque el elemento superior del montón en el conjunto de datos T que almacena elementos ordenados;
En este momento, el montón se ajustará al nuevo montón mínimo;
Repita los pasos 3 y 4 hasta que no queden elementos en el montón;
En este punto, se obtiene un nuevo conjunto de datos T, en el que los elementos están ordenados de pequeño a grande.

Los pasos del algoritmo de clasificación del montón máximo son los siguientes:

Apila todos los elementos en un montón máximo;
Saque y elimine el elemento superior del montón y coloque el elemento superior del montón en el conjunto de datos T que almacena elementos ordenados;
En este momento, el montón se ajustará al nuevo montón máximo;
Repita los pasos 3 y 4 hasta que no queden elementos en el montón;
En este punto, se obtiene un nuevo conjunto de datos T, en el que los elementos están ordenados de mayor a menor.
Complejidad del tiempo: O (Nlog N). N es el número de elementos en el montón.

Complejidad espacial: O (N). N es el número de elementos en el montón.