Montón binario

Ejemplo de un max-heap binario completo

Ejemplo de un montón binario completo de min

Un montón binario es una estructura de datos de montón que toma la forma de un árbol binario. Los montones binarios son una forma común de implementar colas de prioridad. El montón binario fue introducido por J. W. J. Williams en 1964, como una estructura de datos para heapsort.

Un montón binario se define como un árbol binario con dos restricciones adicionales:

• Forma de propiedad: un montón binario es un árbol binario completo; es decir, todos los niveles del árbol, excepto posiblemente el último (deepest) están completamente llenos, y, si el último nivel del árbol no está completo, los nodos de ese nivel se llenan de izquierda a derecha.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

Los montones donde la clave principal es mayor o igual que (≥) las claves secundarias se denominan montones máximos; aquellos en los que es menor o igual que (≤) se denominan min-heaps. Se conocen algoritmos eficientes (tiempo logarítmico) para las dos operaciones necesarias para implementar una cola de prioridad en un montón binario: insertar un elemento y eliminar el elemento más pequeño o más grande de un montón mínimo o máximo, respectivamente. Los montones binarios también se emplean comúnmente en el algoritmo de clasificación heapsort, que es un algoritmo en el lugar porque los montones binarios se pueden implementar como una estructura de datos implícita, almacenando claves en una matriz y usando sus posiciones relativas dentro de esa matriz para representar relaciones padre-hijo..

Operaciones de montón

Tanto las operaciones de inserción como las de eliminación primero modifican el montón para ajustarse a la propiedad de forma, agregando o quitando del final del montón. Luego, la propiedad del montón se restaura recorriendo hacia arriba o hacia abajo el montón. Ambas operaciones toman O(log n) tiempo.

Insertar

Para agregar un elemento a un montón, podemos realizar este algoritmo:

1. Añadir el elemento al nivel inferior del montón en el espacio abierto más izquierdo.
2. Compare el elemento añadido con su padre; si están en el orden correcto, pare.
3. Si no, cambie el elemento con su padre y vuelva al paso anterior.

Los pasos 2 y 3, que restauran la propiedad del montón comparando y posiblemente intercambiando un nodo con su padre, se denominan operación up-heap (también conocida como bubble-up, percolar, tamizar, gotear, nadar, heapify-up, o cascade-up).

La cantidad de operaciones requeridas depende solo de la cantidad de niveles que el nuevo elemento debe subir para satisfacer la propiedad del montón. Por lo tanto, la operación de inserción tiene una complejidad de tiempo en el peor de los casos de O(log n). Para un montón aleatorio y para inserciones repetidas, la operación de inserción tiene una complejidad de caso promedio de O(1).

Como ejemplo de inserción de montón binario, supongamos que tenemos un montón máximo

y queremos agregar el número 15 al montón. Primero colocamos el 15 en la posición marcada por la X. Sin embargo, la propiedad del montón se viola ya que 15 > 8, por lo que necesitamos intercambiar el 15 y el 8. Entonces, tenemos el montón con el siguiente aspecto después del primer intercambio:

Sin embargo, la propiedad del montón todavía se infringe desde 15 > 11, por lo que debemos cambiar de nuevo:

que es un montón máximo válido. No hay necesidad de verificar el hijo izquierdo después de este paso final: al principio, el montón máximo era válido, lo que significa que la raíz ya era mayor que su hijo izquierdo, por lo que reemplazar la raíz con un valor aún mayor mantendrá la propiedad que cada nodo es mayor que sus hijos (11 > 5; si 15 > 11, y 11 > 5, luego 15 > 5, debido a la relación transitiva).

Extraer

El procedimiento para eliminar la raíz del montón (extrayendo efectivamente el elemento máximo en un montón máximo o el elemento mínimo en un montón mínimo) manteniendo la propiedad del montón es el siguiente:

1. Reemplaza la raíz del montón con el último elemento en el último nivel.
2. Compare la nueva raíz con sus hijos; si están en el orden correcto, pare.
3. Si no, cambie el elemento con uno de sus hijos y vuelva al paso anterior. (Swap con su hijo menor en un min-heap y su hijo mayor en un max-heap.)

Los pasos 2 y 3, que restauran la propiedad del montón comparando y posiblemente intercambiando un nodo con uno de sus hijos, se denominan bajar montón (también conocido como burbuja-abajo, percolado hacia abajo, tamizado hacia abajo, hundido hacia abajo, goteo hacia abajo, heapify-down, cascade-down, extract-min o extract-max, o simplemente heapify) operación.

Entonces, si tenemos el mismo montón máximo que antes

Quitamos el 11 y lo reemplazamos por el 4.

Ahora se viola la propiedad del montón ya que 8 es mayor que 4. En este caso, intercambiar los dos elementos, 4 y 8, es suficiente para restaurar la propiedad del montón y no necesitamos intercambiar más elementos:

El nodo que se mueve hacia abajo se intercambia con el más grande de sus hijos en un montón máximo (en un montón mínimo se intercambiaría con su hijo más pequeño), hasta que satisfaga la propiedad del montón en su nueva posición. Esta funcionalidad se logra mediante la función Max-Heapify como se define a continuación en pseudocódigo para un montón respaldado por matriz A de longitud longitud( A). A se indexa a partir de 1.

// Realizar una operación de baja altura o heapify-down para un salto máximo
// A: un array que representa el montón, indexado a partir de 1
// i: el índice para empezar cuando se acelera
Max-Heapify()A, i):
 izquierda ← 2×i derecho ← 2×i + 1
 más grande ← i si izquierda ≤ longitud()A) y A[izquierda] A[A]más grande] entonces:
 más grande ← izquierda
 si derecho ≤ longitud()A) y A[derecho] A[más grande] entonces:
 más grande ← derecho si más grande ل i entonces:
 Swap A[i] y A[más grande]
 Max-Heapify()A, más grande)

Para que el algoritmo anterior vuelva a acumular correctamente la matriz, ningún nodo además del nodo en el índice i y sus dos hijos directos pueden violar la propiedad del montón. La operación de almacenamiento dinámico (sin el intercambio anterior) también se puede usar para modificar el valor de la raíz, incluso cuando no se elimina un elemento.

En el peor de los casos, la nueva raíz debe intercambiarse con su elemento secundario en cada nivel hasta que alcance el nivel inferior del montón, lo que significa que la operación de eliminación tiene una complejidad de tiempo relativa a la altura del árbol, o O (iniciar sesión n).

Insertar y luego extraer

Insertar un elemento y luego extraerlo del montón se puede hacer de manera más eficiente que simplemente llamar a las funciones de inserción y extracción definidas anteriormente, lo que implicaría una operación de montón ascendente y descendente. En su lugar, podemos hacer solo una operación downheap, de la siguiente manera:

1. Compare si el elemento que estamos empujando o la parte superior del montón es mayor (asumiendo un montón máximo)
2. Si la raíz del montón es mayor:
   1. Reemplazar la raíz con el nuevo elemento
   2. Down-heapify starting from the root
3. Else, devuelve el artículo que estamos empujando

Python proporciona una función de este tipo para la inserción y luego la extracción llamada "heappushpop", que se parafrasea a continuación. Se supone que la matriz del montón tiene su primer elemento en el índice 1.

// Empuja un nuevo elemento a un montón (max) y luego extrae la raíz del montón resultante.
// Salto: un array que representa el montón, indexado a 1
// Tema: un elemento para insertar
// Devuelve el mayor de los dos entre Tema y la raíz de Salto.
Push-Pop()Salto: Lista de contactos Tema: T) - título T:
 si Salto no está vacío y heap[1] Tema entonces: / / / / se hizo si min salto
 Swap Salto[1] Tema_downheapSalto a partir del índice 1)
 retorno Tema

Se puede definir una función similar para abrir y luego insertar, que en Python se llama "heapreplace":

// Extraiga la raíz del montón, y empuje un nuevo elemento
// Salto: un array que representa el montón, indexado a 1
// Tema: un elemento para insertar
// Devuelve la raíz actual de SaltoSustitución()Salto: Lista de contactos Tema: T) - título T:
 Swap Salto[1] Tema_downheapSalto a partir del índice 1)
 retorno Tema

Buscar

Encontrar un elemento arbitrario lleva O(n) tiempo.

Eliminar

La eliminación de un elemento arbitrario se puede hacer de la siguiente manera:

1. Encontrar el índice i{displaystyle i} del elemento que queremos eliminar
2. Cierre este elemento con el último elemento
3. Abajo-heapify or up-heapify to restore the heap property. En un max-heap (min-heap), el up-heapify sólo se requiere cuando la nueva clave del elemento i{displaystyle i} es mayor (smaller) que el anterior porque sólo se podría violar la propiedad de heap del elemento padre. Asumiendo que la propietaria del montón era válida entre el elemento i{displaystyle i} y sus hijos antes del intercambio de elementos, no puede ser violado por un valor clave más grande (pequeño). Cuando la nueva clave es menos (más grande) que la anterior, entonces sólo se requiere una baja-heapificación debido a que la propiedad de la pila sólo puede ser violada en los elementos del niño.

Tecla de disminución o aumento

La operación de tecla de disminución reemplaza el valor de un nodo con un valor dado con un valor más bajo, y la operación de tecla de aumento hace lo mismo pero con un valor más alto. Esto implica encontrar el nodo con el valor dado, cambiar el valor y luego aumentar o reducir el almacenamiento dinámico para restaurar la propiedad del almacenamiento dinámico.

La tecla de disminución se puede hacer de la siguiente manera:

1. Encontrar el índice del elemento que queremos modificar
2. Disminuir el valor del nodo
3. Down-heapify (assuming a max heap) para restaurar la propiedad heap

La clave de aumento se puede hacer de la siguiente manera:

1. Encontrar el índice del elemento que queremos modificar
2. Aumentar el valor del nodo
3. Up-heapify (suponiendo un montón máximo) para restaurar la propiedad de montón

Construyendo un montón

La creación de un montón a partir de una matriz de elementos de entrada n se puede hacer comenzando con un montón vacío y luego insertando sucesivamente cada uno elemento. Este enfoque, llamado Williams' después del inventor de los montones binarios, se ve fácilmente que se ejecuta en O(n log n) time: realiza n inserciones en O(log n) cuestan cada uno.

Sin embargo, el método de Williams es suboptimal. Un método más rápido (debido a Floyd) comienza poniendo arbitrariamente los elementos en un árbol binario, respetando la propiedad de la forma (el árbol podría ser representado por un array, véase abajo). Luego, comenzando desde el nivel más bajo y moviéndose hacia arriba, clavija la raíz de cada subárbol hacia abajo como en el algoritmo de eliminación hasta que se restablezca la propiedad del montón. Más específicamente si todos los subárboles comienzan en cierta altura h{displaystyle h} ya han sido "heapificados" (el nivel más inferior correspondiente a h=0{displaystyle h=0}), los árboles en altura h+1{displaystyle h+1} puede ser amontonado enviando su raíz por el camino de los niños de máximo valor al construir un montón máximo, o los niños de valor mínimo al construir un montón. Este proceso requiere O()h){displaystyle O(h)} operaciones por nodo. En este método la mayoría de la heapificación tiene lugar en los niveles inferiores. Desde la altura del montón es ⌊ ⌊ log⁡ ⁡ n⌋ ⌋ {displaystyle lfloor log nrfloor }, el número de nodos en altura h{displaystyle h} es ≤ ≤ 2⌊ ⌊ log⁡ ⁡ n⌋ ⌋ 2h≤ ≤ n2h{displaystyle leq {frac {2^{lfloor log nrfloor }{2^ {h}leq {fn} {fn} {fnK}}} {fn}}} {fn}}} {fn}} {fn}}}} {fn}}}}} {fn}}}} {fn}}}}}. Por lo tanto, el costo de amontonar todos los subárboles es:

.. h=0⌊ ⌊ log⁡ ⁡ n⌋ ⌋ n2hO()h)=O()n.. h=0⌊ ⌊ log⁡ ⁡ n⌋ ⌋ h2h)=O()n.. h=0JUEGO JUEGO h2h)=O()n){displaystyle {begin{aligned}sum ################################################################################################################################################################################################################################################################ {fn} {fn} {fn}} {fn} {fn}} {fn}fnfn} {fn} {fn}} {fn}} {fn}}}} {fn} {fn}fn}}}fn}}fn} {fn}}}f}}}f}}}}}}f}}fn}fn}fnfn}}}}}fnfnfnfnfn}fnfn}}fnfnfn}}}}}}}}}}}}fnfnfnfn}}fn}}fn}fnfnfnfnfnfn}fn}fn}fnfnfn}}fn}}}fnfn}}}}}} ################################################################################################################################################################################################################################################################ ¿Por qué?

Esto utiliza el hecho de que la serie infinita dada .. i=0JUEGO JUEGO i/2i{textstyle sum _{i=0} {infty }i/2{i} converge.

Se sabe que el valor exacto de lo anterior (el peor número de comparaciones durante la construcción del montón) es igual a:

2n− − 2s2()n)− − e2()n){displaystyle 2n-2s_{2}(n)-e_{2}(n)},

donde s₂(n) es la suma de todos los dígitos del representación binaria de n y e₂(n) es el exponente de 2 en la factorización prima de n.

El caso promedio es más complejo de analizar, pero se puede demostrar que se aproxima asintóticamente a 1.8814 n − 2 log₂n + O(1).

La función Build-Max-Heap que sigue, convierte una matriz A que almacena un árbol binario con n nodos en un montón máximo mediante el uso repetido de Max-Heapify (down-heapify para un montón máximo) de forma ascendente. Los elementos de la matriz indexados por piso(n/2) + 1, piso(n/2) + 2,..., n son todas las hojas del árbol (suponiendo que los índices comiencen en 1); por lo tanto, cada uno es un montón de un elemento y no es necesario acumularlo hacia abajo. Se ejecuta Build-Max-Heap Max-Heapify en cada uno de los nodos de árbol restantes.

Build-Max-Heap ()A):
 para cada uno índice i desde planta baja()longitud()A)/2) abajo 1 hacer: Max-Heapify()A, i)

Implementación de montón

Un pequeño árbol binario completo almacenado en un array

Comparación entre un montón binario y una implementación de array.

Los montones se implementan comúnmente con una matriz. Cualquier árbol binario se puede almacenar en una matriz, pero debido a que un montón binario siempre es un árbol binario completo, se puede almacenar de forma compacta. No se requiere espacio para punteros; en cambio, el padre y los hijos de cada nodo se pueden encontrar mediante la aritmética en los índices de matriz. Estas propiedades hacen que esta implementación de almacenamiento dinámico sea un ejemplo simple de una estructura de datos implícita o una lista de Ahnentafel. Los detalles dependen de la posición raíz, que a su vez puede depender de las restricciones de un lenguaje de programación utilizado para la implementación o de la preferencia del programador. Específicamente, a veces la raíz se coloca en el índice 1, para simplificar la aritmética.

Sea n el número de elementos en el montón y i sea un índice arbitrario válido de la matriz que almacena el montón. Si la raíz del árbol está en el índice 0, con índices válidos del 0 al n − 1, entonces cada elemento a en el índice i tiene

• niños en índices 2i + 1 y 2i + 2
• su padre en el índice planta baja()i − 1) / 2).

Alternativamente, si la raíz del árbol está en el índice 1, con índices válidos del 1 al n, entonces cada elemento a en el índice i tiene

• niños en índices 2i y 2i + 1
• su padre en el índice planta baja()i / 2).

Esta implementación se usa en el algoritmo heapsort que reutiliza el espacio asignado a la matriz de entrada para almacenar el montón (es decir, el algoritmo se realiza en el lugar). Esta implementación también es útil como cola de prioridad. Cuando se utiliza una matriz dinámica, es posible la inserción de un número ilimitado de elementos.

Las operaciones upheap/downheap se pueden establecer en términos de una matriz de la siguiente manera: suponga que la propiedad del montón se cumple para los índices b, b+1,..., e. La función tamizar hacia abajo extiende la propiedad del montón a b−1, b, b+1,..., e. Solo el índice i = b−1 puede violar la propiedad del montón. Sea j el índice del hijo mayor de a[i] (para un montón máximo, o el hijo más pequeño para un mínimo heap) dentro del rango b,..., e. (Si no existe tal índice porque 2i > e entonces la propiedad heap se mantiene para el rango recién extendido y nada necesita ser hecho.) Al intercambiar los valores a[i] y a[j], la propiedad del montón para la posición i se establece. En este punto, el único problema es que la propiedad del montón podría no ser válida para el índice j. La función tamizar hacia abajo se aplica recursivamente al índice j hasta que se establece la propiedad del montón para todos los elementos.

La función de cribado es rápida. En cada paso solo necesita dos comparaciones y un intercambio. El valor del índice en el que está trabajando se duplica en cada iteración, por lo que se requieren como máximo log₂ e pasos.

Para montones grandes y usando memoria virtual, almacenar elementos en una matriz de acuerdo con el esquema anterior es ineficiente: (casi) cada nivel está en una página diferente. Los montones B son montones binarios que mantienen subárboles en una sola página, lo que reduce el número de páginas a las que se accede hasta en un factor de diez.

La operación de fusionar dos montones binarios requiere Θ(n) para montones del mismo tamaño. Lo mejor que puede hacer es (en el caso de la implementación de una matriz) simplemente concatenar las dos matrices de montón y construir un montón del resultado. Un montón en n elementos se puede fusionar con un montón en k elementos usando O(log n log k) comparaciones clave o, en el caso de una implementación basada en punteros, en tiempo O(log n log k). Un algoritmo para dividir un montón en elementos n en dos montones en elementos k y n-k, respectivamente, basado en una nueva vista de montones como se presentó una colección ordenada de submontones. El algoritmo requiere comparaciones O(log n * log n). La vista también presenta un algoritmo nuevo y conceptualmente simple para fusionar montones. Cuando la fusión es una tarea común, se recomienda una implementación de almacenamiento dinámico diferente, como almacenamiento dinámico binomial, que se puede fusionar en O(log n).

Además, se puede implementar un montón binario con una estructura de datos de árbol binario tradicional, pero hay un problema al encontrar el elemento adyacente en el último nivel del montón binario al agregar un elemento. Este elemento se puede determinar algorítmicamente o agregando datos adicionales a los nodos, lo que se denomina "threading" el árbol—en lugar de simplemente almacenar referencias a los hijos, también almacenamos el sucesor en orden del nodo.

Es posible modificar la estructura del montón para hacer posible la extracción del elemento más pequeño y mayor O{displaystyle O.()log⁡ ⁡ n){displaystyle (log n)} tiempo. Para hacer esto, las filas se alternan entre el salto min y el salto máximo. Los algoritmos son aproximadamente iguales, pero, en cada paso, uno debe considerar las filas alternantes con comparaciones alternantes. El rendimiento es aproximadamente el mismo que un salto normal de dirección. Esta idea se puede generalizar a un montón de min-max mediana.

Derivación de ecuaciones índice

En un montón basado en matrices, los elementos secundarios y principales de un nodo se pueden ubicar mediante aritmética simple en el índice del nodo. Esta sección deriva las ecuaciones relevantes para los montones con su raíz en el índice 0, con notas adicionales sobre los montones con su raíz en el índice 1.

Para evitar confusiones, definiremos el nivel de un nodo como su distancia desde la raíz, de modo que la propia raíz ocupa el nivel 0.

Nodos secundarios

Para un nodo general situado en el índice i (a partir de 0), obtendremos primero el índice de su hijo derecho, derecho=2i+2{displaystyle {text{right}=2i+2}.

Deja que node i estar situado en el nivel L, y notar que cualquier nivel l contiene exactamente 2l{displaystyle 2^{l} nodos. Además, hay exactamente 2l+1− − 1{displaystyle 2^{l+1}-1} nodos contenidos en las capas hasta e incluyendo capas l (Piensa en aritmética binaria; 0111...111 = 1000...000 - 1). Porque la raíz está almacenada en 0, la kt nodo se almacenará en el índice ()k− − 1){displaystyle (k-1)}. Reunir estas observaciones produce la siguiente expresión para la índice del último nodo en capa l.

último()l)=()2l+1− − 1)− − 1=2l+1− − 2{displaystyle {text{last}(l)=(2^{l+1}-1=2^{l+1}-2}

Que haya j nodos después del nodo i en la capa L, tal que

i=último()L)− − j=()2L+1− − 2)− − j{displaystyle {begin{alignedat}{2}i= limitquad {text{last}(L)-j\= limitquad (2^{L+1}-2)-jend{alignedat}}}}

Cada uno de estos j los nodos deben tener exactamente 2 hijos, así que debe haber 2j{displaystyle 2j} nodos que separan i's niño derecho desde el final de su capa (L+1{displaystyle L+1}).

derecho=último(L + 1)− − 2j=()2L+2− − 2)− − 2j=2()2L+1− − 2− − j)+2=2i+2{displaystyle {begin{alignedat}{2}{text{right}= limitquad {text{last(L +1)}}-2j\= limitquad (2^{L+2}-2j= limitquad 2(2^{L+1}-2-j)+2=}==quad

Según sea necesario.

Observando que el niño izquierdo de cualquier nodo es siempre 1 lugar antes de su hijo derecho, obtenemos izquierda=2i+1{displaystyle {text{left}=2i+1}.

Si la raíz se encuentra en el índice 1 en lugar de 0, el último nodo en cada nivel es en cambio en el índice 2l+1− − 1{displaystyle 2^{l+1}-1}. Utilizando esto a través de los rendimientos izquierda=2i{displaystyle {text{left}=2i} y derecho=2i+1{displaystyle {text{right}=2i+1} por montones con su raíz en 1.

Nodo principal

Cada nodo es el hijo izquierdo o derecho de su padre, por lo que sabemos que cualquiera de los siguientes es cierto.

1. i=2× × ()padre)+1{displaystyle i=2times ({text{parent}})+1}
2. i=2× × ()padre)+2{displaystyle i=2times ({text{parent}})+2}

Por lo tanto,

padre=i− − 12oi− − 22{displaystyle {text{parent}={frac} {I-1}{2};{textrm {or};{frac}\fnMic} {i-2}{2}}}

Ahora considere la expresión ⌊i− − 12⌋{displaystyle leftlfloor {dfrac Está bien..

Si no i{displaystyle i} es un niño izquierdo, esto da el resultado inmediatamente, sin embargo, también da el resultado correcto si nodo i{displaystyle i} es un niño adecuado. En este caso, ()i− − 2){displaystyle (i-2)} debe ser incluso, y por lo tanto ()i− − 1){displaystyle (i-1)} Debe ser extraño.

⌊i− − 12⌋=⌊i− − 22+12⌋=i− − 22=padre{displaystyle {begin{alignedat}{2}leftlfloor Está bien. =quad leftlfloor {dfrac {I-2}{2}+{dfrac} {1}{2}rightrfloor ################################################################################################################################################################################################################################################################ {i-2}{2}\\\\=text{parent}end{alignedat}}

Por lo tanto, independientemente de si un nodo es un hijo izquierdo o derecho, su padre se puede encontrar mediante la expresión:

padre=⌊i− − 12⌋{displaystyle {text{parent}=leftlfloor Está bien.

Estructuras relacionadas

Dado que la propiedad del montón no especifica el orden de los hermanos en un montón, los dos hijos de un solo nodo se pueden intercambiar libremente a menos que se infrinja la propiedad de forma (comparar con treap). Tenga en cuenta, sin embargo, que en el montón común basado en matrices, el simple intercambio de los elementos secundarios también podría requerir mover los nodos del subárbol secundario para conservar la propiedad del montón.

El montón binario es un caso especial del montón d-ario en el que d = 2.

Resumen de los tiempos de ejecución

Estas son las complejidades de tiempo de varias estructuras de datos de almacenamiento dinámico. Los nombres de las funciones asumen un montón mínimo. Para el significado de "O(f)" y "Θ(f)" ver notación Big O.