Las propiedades del montón
Un montón es un árbol completamente binario, que se puede implementar en realidad a través de una matriz. Una de sus propiedades más importantes es que cualquier nodo es más pequeño que (mayor que) es igual a sus nodos infantiles. El montón con el nodo raíz más pequeño se llama montón más pequeño, y el montón con el nodo de raíz más grande se llama el montón más grande. La siguiente figura muestra un ejemplo de un montón más grande y su representación de matriz, que puede verse intuitivamente que cada nodo es más grande que sus hijos.
Como se puede ver en la figura anterior, los nodos de un árbol completamente binario se pueden organizar en orden desde el número 1 del nodo raíz, correspondiente al índice en la matriz A (tenga en cuenta que el subíndice aquí comienza desde 1). Dado un nodo I, podemos obtener fácilmente su hijo izquierdo es 2i, el niño derecho es 2i+1 y el nodo principal es i/2
Operaciones básicas de montón
Hay dos operaciones básicas para el montón (consulte el montón mínimo como ejemplo a continuación):
Inserte el elemento K: Agregue K directamente al final de la matriz y luego burbujee para ajustar el montón. Operación de burbujas: compare el elemento que se ajustará a su nodo principal, y si es mayor que su nodo principal, cambie hasta que se restablezcan las propiedades del montón.
Extraiga el mayor valor: el mayor valor es el elemento raíz. Luego, elimínelo, deje que el elemento raíz = el último elemento del nodo de hoja y luego burbujee del elemento raíz para ajustar el montón. Operación de burbujas hacia abajo: cada vez, debe seleccionar el nodo infantil más pequeño de los tres nodos para ajustar el nodo, que tiene a los niños izquierdo y derecho para intercambiar (si el más pequeño, no necesita intercambiarse), hasta que las propiedades del montón se restablezcan.
En la práctica, a menudo es necesario construir una matriz desordenada que contenga N elementos en montones. El constructor en la clase de montón a continuación mostrará cómo construir un montón a través del ajuste de burbujas de BubbleDown. El montón es esencialmente un árbol completamente binario, y la altura del árbol siempre es lognlogn. La operación que requiere mucho tiempo de cada operación básica es burbujear y ajustar para cumplir con las propiedades del montón, por lo que su complejidad del tiempo es O (NLOGN) O (NLOGN).
Ejemplo de Java:
// FLOAT public void Swim (int k) {while (k/2> = 1 && menos (pq [k/2], pq [k])) {Exch (pq, k/2, k); k = k/2; }} // hundir sin fregadero vacío privado () {int k = 1; while (2*k <n) {int j = 2*k; if (menos (pq [j], pq [j+1])) j ++; if (menos (pq [k], pq [j])) excch (pq, k, j); de lo contrario rompe; k = j; }} Principio de implementación de clasificación de montón
Se divide en dos pasos:
1. Organizar matrices en orden de montón binario
2. Cambie la posición del nodo raíz y el último nodo, y luego hunde el nodo raíz.
lograr:
Tal vez mi código es ligeramente diferente de la animación anterior, pero los principios básicos son similares.
Public Class HeepSort extiende Basesort {private int n; @Override public void sort (comparable [] a) {n = a.length-1; int k = n/2; while (k> = 1) {sumidero (a, k); K--; } k = 1; while (k <= n) {Exch (a, k, n--); sumidero (a, k); }}}