Montón binario
Un montón binario , una pirámide [1] o un árbol de clasificación es un árbol binario que satisface tres condiciones:
- El valor en cualquier vértice no es menor que los valores de sus descendientes [K 1] .
- La profundidad de todas las hojas (distancia a la raíz) difiere en no más de 1 capa.
- La última capa se llena de izquierda a derecha sin "agujeros".
También hay montones donde el valor en cualquier vértice, por el contrario, no es mayor que los valores de sus descendientes. Estos montones se denominan montón mínimo y los montones descritos anteriormente se denominan montón máximo. A continuación, solo se considera max-heap. Todas las acciones con min-heap se llevan a cabo de manera similar.
Una estructura de datos conveniente para un árbol de clasificación es una matriz A , cuyo primer elemento, A [1] es el elemento en la raíz, y los elementos secundarios del elemento A [ i ] son A [2 i ] y A [2 i +1 ] (al numerar elementos con first). Al numerar elementos desde cero, el elemento raíz es A [0], y los hijos del elemento A [ i ] son A [2 i +1] y A [2 i +2]. Con este método de almacenamiento, las condiciones 2 y 3 se cumplen automáticamente.
La altura del montón se define como la altura del árbol binario. Es decir, es igual al número de aristas en el camino simple más largo que conecta la raíz del montón con una de sus hojas. La altura del montón es , donde N es el número de nodos del árbol.
Funcionalidad
Puede realizar las siguientes operaciones en un montón:
- Agregue un elemento al montón. Complejidad
- Elimina el elemento máximo del montón. Horas Laborales
- Cambia el valor de cualquier elemento. Horas Laborales
En base a estas operaciones, puede realizar las siguientes acciones:
- Convierta una matriz desordenada de elementos en un montón. Complejidad
- Ordene una matriz convirtiéndola en un montón y el montón en una matriz ordenada. Horas Laborales
Aquí está el número de elementos del montón. Complejidad del espacio : para todas las operaciones y actividades anteriores.
En la siguiente sección se proporciona una descripción detallada y los algoritmos de estas acciones y el procedimiento de Heapify necesario para realizarlas.
Procedimientos Básicos
Esta sección presenta los procedimientos básicos para trabajar con un montón.
Restaurando las propiedades del montón
Si uno de los elementos del montón cambia, es posible que ya no satisfaga la propiedad de ordenación. Para restaurar esta propiedad, use el procedimiento Heapify. Restaura la propiedad del montón en un árbol cuyos subárboles izquierdo y derecho la satisfacen. Este procedimiento toma como entrada una matriz de elementos A e índice i . Restaura la propiedad de ordenamiento en todo el subárbol cuya raíz es el elemento A [ i ].
Si el i -ésimo elemento es mayor que sus hijos, todo el subárbol ya es un montón y no es necesario hacer nada. De lo contrario, intercambiamos el i -ésimo elemento con el mayor de sus hijos, después de lo cual ejecutamos Heapify para este hijo.
El procedimiento se completa a tiempo .
Heapify( A , i ) left ← 2 i right ← 2 i +1 heap_size - el número de elementos en el montón más grande ← i if left ≤ A . heap_size y A [ izquierda ] > A [ mayor ] entonces mayor ← izquierda si derecha ≤ A. heap_size y A [ derecha ] > A [ más grande ] luego más grande ← derecha si más grande ≠ i luego Intercambiar A [ i ] ↔ A [ más grande ] Heapify ( A , más grande )
Para los lenguajes que no admiten la optimización de recursividad de cola automática , la eficiencia de implementación se puede mejorar eliminando la recursividad.
Construyendo un montón
Este procedimiento está diseñado para crear un montón a partir de una matriz desordenada de datos de entrada.
Tenga en cuenta que si ejecuta Heapify en todos los elementos de la matriz A, desde el último hasta el primero, se convertirá en un montón. De hecho, es fácil probar por inducción que en el momento en que se ejecuta Heapify(A, i), todos los subárboles cuyas raíces tienen un índice mayor que i son montones y, por lo tanto, después de ejecutar Heapify(A, i), todos subárboles cuyas raíces tienen un índice no menor que i.
Además, Heapify(A,i) no hace nada si i>N/2 (cuando se numera desde el primer elemento), donde N es el número de elementos de la matriz. De hecho, tales elementos no tienen hijos, por lo tanto, los subárboles correspondientes ya son montones, ya que contienen solo un elemento.
Por lo tanto, basta con llamar a Heapify para todos los elementos de la matriz A, comenzando (cuando se numera desde el primer elemento) desde el -ésimo y terminando con el primero.
Build_Heap( A ) A . heap_size ← A . longitud para i ← ⌊ A . length /2⌋ downto 1 do Heapify( A , i )![[N/2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/45c0ad27874a87a53ba4fdef0a0ed24d22fb7f99)
Aunque hay n/2 llamadas a la función Heapify aquí con complexidad , se puede demostrar que el tiempo de ejecución es [1] .
Ordenar montón
El procedimiento Heapsort ordena una matriz sin usar memoria adicional en el tiempo .
Para entender su funcionamiento, podemos imaginar que hemos intercambiado el primer elemento (es decir, la raíz) con el último. Entonces el último elemento será el más grande. Si después de eso excluimos el último elemento del montón (es decir, reducimos formalmente su longitud en 1), los primeros N-1 elementos cumplirán todas las condiciones del montón, excepto quizás la raíz. Si llama a Heapify, los primeros elementos N-1 se convertirán en un montón y el último será más grande que todos ellos. Al repetir estos pasos N-1 veces, ordenaremos la matriz.
Heapsort( A ) Build_Heap( A ) para i ← A . longitud hasta 1 hacer Swap A [1] ↔ A [ i ] A . heap_size ← A . montón_tamaño -1 Apilar( A ,1)Cambiar el valor de un elemento
El procedimiento Heap_Increase_Key reemplaza un elemento de montón con una nueva clave con un valor mayor o igual que el valor del elemento original . Normalmente, este procedimiento se usa para agregar un elemento arbitrario al montón. Complejidad del tiempo .
Si el elemento es menor que su padre, se cumple la condición 1 para todo el árbol y no es necesario hacer nada más. Si es más grande, intercambiamos lugares con su padre. Si después de eso el padre es más grande que el abuelo, cambiamos al padre por el abuelo, y así sucesivamente. En otras palabras, un elemento demasiado grande flota hacia arriba.
Heap_Increase_Key( A , i , key ) if key < A [ i ] then error "La nueva clave es más pequeña que la anterior" A [ i ] ← key while i > 1 and A [⌊ i /2⌋] < A [ i ] hacer Intercambiar A [ i ] ↔ A [⌊ i /2⌋] i ← ⌊ i /2⌋En el caso de que sea necesario reducir el valor de un elemento, puede llamar a Heapify.
Agregar un elemento
Realiza la adición de un elemento al montón a tiempo .
Agregar un elemento arbitrario al final del montón y restaurar la propiedad de orden con Heap_Increase_Key.
Heap_Insert( A , clave ) A . heap_size ← A . heap_size +1 A [ A . montón_tamaño ] ← -∞ Heap_Increase_Key( A , A . heap_size , clave)Extrayendo el elemento máximo
Recupera el elemento máximo del montón a tiempo .
La extracción se realiza en cuatro pasos:
- el valor del elemento raíz (es el máximo) se almacena para su posterior devolución
- el último elemento se copia a la raíz y luego se elimina del montón
- llamado Heapify en la raíz
- se devuelve el elemento almacenado
Véase también
Enlaces
- ↑ 1 2 Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capítulo 6. Heapsort // Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - S. 178 - 193. - ISBN 5-8459-0857-4 .
Comentarios
- ↑ Si se invierte el orden de clasificación, el valor en cualquier nodo no debe ser mayor que los valores de sus descendientes.
| Estructuras de datos | |
|---|---|
| Liza | |
| Árboles | |
| cuenta | |
| Otro | |
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |