¿Qué es la clasificación en montón?

El concepto Heapsort se refiere a un algoritmo de clasificación diseñado utilizando una estructura de datos como un árbol apilado (montón). Es un tipo de clasificación por selección. Puede utilizar las características de las matrices para localizar rápidamente el elemento en un índice específico. El montón se divide en un montón de raíz grande y un montón de raíz pequeño, que es un árbol binario completo. El requisito de un montón raíz grande es que el valor de cada nodo no sea mayor que el valor de su nodo padre, es decir, A[PARENT[i]] gt; En la clasificación no descendente de una matriz, se debe utilizar un montón raíz grande, porque de acuerdo con los requisitos de un montón raíz grande, el valor más grande debe estar en la parte superior del montón.

Origen

Los ganadores del premio Computer Pioneer Award de 1991, Robert W. Floyd y J. Williams, profesores del Departamento de Ciencias de la Computación de la Universidad de Stanford, co-inventaron el famoso algoritmo de clasificación de montón. (Clasificación de montón) en 1964.

Introducción

La clasificación del montón aprovecha la característica de que la clave registrada en la parte superior del montón raíz grande (o montón raíz pequeño) es la más grande (o la más pequeña), de modo que se puede seleccionar en el área desordenada actual. El registro de las palabras clave más grandes (o más pequeñas) se vuelve simple.

(1) La idea básica de utilizar la clasificación de montón raíz grande

① Primero construya el archivo inicial R [1..n] en un montón raíz grande, que es el área desordenada inicial

② Luego intercambie el registro R[1] con la palabra clave más grande (es decir, la parte superior del montón) y el último registro R[n] en el área desordenada, obteniendo así una nueva área desordenada R[1.. n-1] y área ordenada R[n], y satisface R[1..n-1].keys≤R[n].key

③Desde la nueva raíz R [1 después del intercambio] puede violar las propiedades del montón, por lo que el área desordenada actual R [1..n-1] debe ajustarse a un montón. Luego intercambie el registro R[1] con la palabra clave más grande en R[1..n-1] y el último registro R[n-1] en el intervalo nuevamente, obteniendo así una nueva área desordenada R[1.. n- 2] y el área ordenada R[n-1..n], y aún satisfacen la relación R[1..n-2].keys≤R[n-1..n].keys, también debemos cambiar R [1..n-2] se ajusta al montón.

......

Hasta que solo quede un elemento en el área desordenada.

(2) Operaciones básicas del algoritmo de clasificación del montón raíz grande:

① Construir un montón es un proceso de ajuste constante del montón. Comience a ajustar desde len/2. hasta llegar a los primeros nodos, donde len es el número de elementos en el montón. El proceso de construcción de un montón es un proceso lineal. El proceso de ajuste del montón siempre se llama de len/2 a 0, lo que equivale a o(h1) o(h2)... o(hlen/2) donde h. representa la profundidad del nodo, len/2 Representa el número de nodos. Este es un proceso de suma y el resultado es lineal O (n).

②Montón de ajuste: el montón de ajuste se utilizará en el proceso de construcción del montón y también se utilizará en el proceso de clasificación del montón. La idea de utilizar es comparar el nodo i y sus nodos secundarios izquierdo (i), derecho (i) y seleccionar el valor más grande (o más pequeño) de los tres si el valor más grande (más pequeño) no es el nodo i. pero uno de sus nodos secundarios, allí, el nodo i interactúa con el nodo y luego llama al proceso de ajuste del montón. Este es un proceso recursivo. La complejidad temporal del proceso de ajuste del montón está relacionada con la profundidad del montón. Es una operación de lgn, porque se ajusta a lo largo de la dirección de la profundidad.

③Clasificación del montón: la clasificación del montón se realiza mediante los dos procesos anteriores. El primero es construir un montón basado en elementos. Luego extraiga el nodo raíz del montón (generalmente cámbielo por el último nodo), continúe el proceso de ajuste del montón con los primeros nodos len-1 y luego extraiga el nodo raíz hasta que se hayan eliminado todos los nodos. La complejidad temporal del proceso de clasificación del montón es O (nlgn).

Debido a que la complejidad temporal de construir un montón es O (n) (una llamada); la complejidad temporal de ajustar el montón es lgn y se llama n-1 veces, por lo que la complejidad temporal de la clasificación del montón es O (nlgn) [ 2]

Nota:

① Solo es necesario ordenar n-1 y seleccionar las palabras clave n-1 más grandes para hacer los archivos en orden creciente.

② Ordenar con un montón raíz pequeño es similar a usar un montón raíz grande, excepto que los resultados de la clasificación están en orden descendente. La clasificación en montón es lo opuesto a la clasificación por selección directa: en cualquier momento, en la clasificación en montón, el área desordenada siempre está antes del área ordenada, y el área ordenada se expande gradualmente de atrás hacia adelante al final del vector original hasta alcanzar la totalidad. vector

Características

HeapSort es una clasificación de selección de árbol. Las características de la clasificación del montón son: durante el proceso de clasificación, R [l..n] se considera como la estructura de almacenamiento secuencial de un árbol binario completo, y la relación intrínseca entre el nodo padre y el nodo secundario en el árbol binario completo es utilizado (ver Estructura de almacenamiento secuencial del árbol binario), seleccione el registro con la palabra clave más grande (o más pequeña) en el área desordenada actual

Análisis de algoritmos

El tiempo de clasificación del montón se compone principalmente de establecer el montón inicial y repetir La sobrecarga de tiempo para reconstruir estas dos partes del montón consta de ellas, las cuales se implementan llamando a Heapify.

Rendimiento medio: O(N*logN).

Otro rendimiento: debido a la gran cantidad de comparaciones necesarias para construir el montón inicial, la clasificación del montón no es adecuada para archivos con una pequeña cantidad de registros. La clasificación del montón es una clasificación in situ y el espacio auxiliar es O (1). Es un método de clasificación inestable. (La estabilidad de la clasificación significa que si hay dos elementos idénticos en la secuencia ordenada, sus posiciones relativas no cambiarán antes y después de la clasificación).