Montón binario

Variante de la estructura de datos del montón

Ejemplo de un montón máximo binario completo

Ejemplo de un montón mínimo binario completo

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 . ^{[1] : 162–163} El montón binario fue introducido por JWJ Williams en 1964, como una estructura de datos para la clasificación de montón . ^[2]

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

• Propiedad de forma: un montón binario es un árbol binario completo ; es decir, todos los niveles del árbol, excepto posiblemente el último (el más profundo), 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.
• Propiedad del montón: la clave almacenada en cada nodo es mayor o igual a (≥) o menor o igual a (≤) las claves de los hijos del nodo, de acuerdo con algún orden total .

Los montones en los que la clave principal es mayor o igual que (≥) las claves secundarias se denominan max-heaps ; 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 min-heap o max-heap, respectivamente. Los montones binarios también se emplean comúnmente en el algoritmo de ordenamiento heapsort , que es un algoritmo in situ porque los montones binarios se pueden implementar como una estructura de datos implícita , almacenando claves en una matriz y utilizando sus posiciones relativas dentro de esa matriz para representar relaciones padre-hijo.

Operaciones de montón

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

Insertar

Para insertar un elemento en un montón, realizamos los siguientes pasos:

1. Agrega el elemento al nivel inferior del montón en el espacio abierto más a la izquierda.
2. Compare el elemento agregado con su padre; si están en el orden correcto, deténgase.
3. En caso contrario, intercambie 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 , percolate-up , sift-up , trickle-up , swim-up , heapify-up , cascade-up o fix-up ).

La cantidad de operaciones requeridas depende únicamente de la cantidad de niveles que el nuevo elemento debe alcanzar para satisfacer la propiedad del montón. Por lo tanto, la operación de inserción tiene una complejidad temporal 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 en el caso promedio de O(1). ^{[4] [5]}

Como ejemplo de inserción de montón binario, digamos 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 que se ve de la siguiente manera después del primer intercambio:

Sin embargo, la propiedad del montón aún se viola ya que 15 > 11 , por lo que necesitamos intercambiar nuevamente:

que es un max-heap válido. No hay necesidad de verificar el hijo izquierdo después de este paso final: al comienzo, el max-heap 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 de que cada nodo es mayor que sus hijos ( 11 > 5 ; si 15 > 11 y 11 > 5 , entonces 15 > 5 , debido a la relación transitiva ).

Extracto

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) mientras se conserva la propiedad del montón es el siguiente:

1. Reemplace la raíz del montón con el último elemento del último nivel.
2. Compare la nueva raíz con sus hijos; si están en el orden correcto, deténgase.
3. En caso contrario, intercambie el elemento con uno de sus hijos y vuelva al paso anterior. (Intercambie con su hijo más pequeño en un montón mínimo y con su hijo más grande en un montón máximo).

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 operación down-heap (también conocida como bubble-down , percolate-down , sift-down , sink-down , trickle down , heapify-down , cascade-down , fix-down , extract-min o extract-max , o simplemente heapify ).

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 mayor 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 A respaldado por una matriz de longitud length ( A ). A se indexa a partir de 1.

// Realizar una operación de down-heap o heapify-down para un max-heap// A : una matriz que representa el montón, indexada a partir de 1// i : el índice en el que se debe comenzar al apilar hacia abajo Max-Heapify ( A , i ): izquierda ← 2× i  derecha ← 2× i + 1 más grande ← i  si  izquierda ≤ longitud ( A ) y  A [ izquierda ] > A [ mayor ] entonces : mayor ← izquierda 
 si  derecha ≤ longitud ( A ) y  A [ derecha ] > A [ mayor ] entonces : mayor ← derecha  Si  el mayor ≠ i  entonces : intercambia  A [ i ] y A [ el mayor ] Max-Heapify ( A , el mayor )

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

En el peor de los casos, la nueva raíz debe intercambiarse con su hijo en cada nivel hasta que alcanza 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, u O(log n ).

Insertar y luego extraer

La inserción y posterior extracción de un elemento del montón se puede realizar de manera más eficiente que simplemente invocar las funciones de inserción y extracción definidas anteriormente, lo que implicaría una operación upheapy downheap. En cambio, podemos realizar solo una downheapoperación, de la siguiente manera:

1. Compare si el elemento que estamos empujando o la parte superior del montón es mayor (suponiendo un montón máximo)
2. Si la raíz del montón es mayor:
   1. Reemplace la raíz con el nuevo elemento
   2. Descomponer el montón comenzando desde la raíz
3. De lo contrario, devuelva el artículo que estamos impulsando.

Python proporciona una función para la inserción y luego la extracción llamada "heappushpop", que se parafrasea a continuación. ^{[6] [7]} Se supone que la matriz de montón tiene su primer elemento en el índice 1.

// Empuja un nuevo elemento a un montón (máximo) y luego extrae la raíz del montón resultante.// montón : una matriz que representa el montón, indexada en 1// elemento : un elemento para insertar// Devuelve el mayor de los dos entre el elemento y la raíz del montón . Push-Pop ( montón : List<T>, elemento : T) -> T: si  el montón no está vacío y montón[1] > elemento  entonces : // < si el montón mínimo intercambia  montón [1] y elemento _downheap( montón que comienza desde el índice 1) devuelve  elemento

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

// Extrae la raíz del montón y envía un nuevo elemento// montón : una matriz que representa el montón, indexada en 1// elemento : un elemento para insertar// Devuelve la raíz actual del montón Reemplazar ( montón : List<T>, elemento : T) -> T: intercambia  montón [1] y elemento _downheap( montón que comienza desde el índice 1) devuelve  elemento

Buscar

Encontrar un elemento arbitrario toma O(n) tiempo.

Borrar

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

1. Encuentra el índice del elemento que queremos eliminar ${\displaystyle i}$
2. Intercambia este elemento con el último elemento.
3. Down-heapify o up-heapify para restaurar la propiedad del montón. En un montón máximo (mín.), up-heapify solo es necesario cuando la nueva clave del elemento es mayor (menor) que la anterior porque solo se puede violar la propiedad del montón del elemento padre. Suponiendo que la propiedad del montón era válida entre el elemento y sus hijos antes del intercambio de elementos, no puede ser violada por un valor de clave ahora mayor (menor). Cuando la nueva clave es menor (mayor) que la anterior, solo se requiere down-heapify porque la propiedad del montón solo puede ser violada en los elementos hijos. ${\displaystyle i}$ ${\displaystyle i}$

Tecla para aumentar o disminuir

La operación de disminución de clave reemplaza el valor de un nodo con un valor dado por un valor menor, y la operación de aumento de clave hace lo mismo pero con un valor mayor. Esto implica encontrar el nodo con el valor dado, cambiar el valor y luego amontonar hacia abajo o hacia arriba para restaurar la propiedad del montón.

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

1. Encuentra el índice del elemento que queremos modificar
2. Disminuir el valor del nodo
3. Descomponer el montón (asumiendo un montón máximo) para restaurar la propiedad del montón

El incremento de la clave se puede realizar de la siguiente manera:

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

Construyendo un montón

Para construir un montón a partir de una matriz de n elementos de entrada, se puede empezar con un montón vacío y luego insertar sucesivamente cada elemento. Este enfoque, llamado método de Williams en honor al inventor de los montones binarios, se ejecuta fácilmente en tiempo O ( n log n ) : realiza n inserciones a un costo O (log n ) cada una. ^[a]

Sin embargo, el método de Williams no es óptimo. Un método más rápido (debido a Floyd ^[8] ) comienza colocando arbitrariamente los elementos en un árbol binario, respetando la propiedad de forma (el árbol podría estar representado por una matriz, ver más abajo). Luego, comenzando desde el nivel más bajo y moviéndose hacia arriba, tamiza la raíz de cada subárbol hacia abajo como en el algoritmo de eliminación hasta que se restablezca la propiedad de montón. Más específicamente, si todos los subárboles que comienzan en cierta altura ya han sido "amontonados" (el nivel más bajo corresponde a ), los árboles en la altura pueden amontonarse enviando su raíz hacia abajo a lo largo de la ruta de los hijos de valor máximo al construir un montón máximo, o los hijos de valor mínimo al construir un montón mínimo. Este proceso requiere operaciones (swaps) por nodo. En este método, la mayor parte de la amontonación tiene lugar en los niveles inferiores. Dado que la altura del montón es , la cantidad de nodos en la altura es . Por lo tanto, el costo de amontonar todos los subárboles es: ${\displaystyle h}$ ${\displaystyle h=0}$ ${\displaystyle h+1}$ ${\displaystyle O(h)}$ ${\displaystyle \lfloor \log n\rfloor }$ ${\displaystyle h}$ ${\displaystyle \leq {\frac {2^{\lfloor \log n\rfloor }}{2^{h}}}\leq {\frac {n}{2^{h}}}}$

${\displaystyle {\begin{aligned}\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {n}{2^{h}}}O(h)&=O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {h}{2^{h}}}\right)\\&=O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)\\&=O(n)\end{aligned}}}$

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

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

${\displaystyle 2n-2s_{2}(n)-e_{2}(n)}$, ^{[9] [b]}

donde s ₂ ( n ) es la suma de todos los dígitos de la 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) comparaciones. ^{[10] [11]}

La función Build-Max-Heap que sigue convierte una matriz A que almacena un árbol binario completo con n nodos en un montón máximo mediante el uso repetido de Max-Heapify (hacia abajo el montón para un montón máximo) de manera ascendente. Los elementos de la matriz indexados por floor ( n /2) + 1 , floor ( n /2) + 2 , ..., n son todas hojas del árbol (suponiendo que los índices comienzan en 1); por lo tanto, cada uno es un montón de un elemento y no necesita ser reducido al montón. Build-Max-Heap ejecuta Max-Heapify en cada uno de los nodos restantes del árbol.

Build-Max-Heap ( A ): para cada índice i  desde  el piso ( longitud ( A )/2) hasta 1 hacer:  Max-Heapify ( A , i )

Implementación de montón

Un pequeño árbol binario completo almacenado en una matriz

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

Los montículos se implementan comúnmente con una matriz . Cualquier árbol binario se puede almacenar en una matriz, pero debido a que un montículo binario es siempre 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 aritmética en los índices de la matriz. Estas propiedades hacen que esta implementación del montículo sea un ejemplo simple de una estructura de datos implícita o una lista Ahnentafel . Los detalles dependen de la posición de la 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 e i un índice válido arbitrario de la matriz que almacena el montón. Si la raíz del árbol está en el índice 0, con índices válidos de 0 a n − 1, entonces cada elemento a en el índice i tiene

• niños en los índices 2 i + 1 y 2 i + 2
• su padre en el índice piso (( 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 los índices 2 i y 2 i +1
• su padre en el índice piso ( i / 2).

Esta implementación se utiliza en el algoritmo de ordenación por heap , que reutiliza el espacio asignado a la matriz de entrada para almacenar el heap (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 una cantidad ilimitada de elementos.

Las operaciones upheapor downheappueden entonces enunciarse en términos de una matriz de la siguiente manera: supongamos que la propiedad heap se cumple para los índices b , b +1, ..., e . La función sift-down extiende la propiedad heap a b −1, b , b +1, ..., e . Solo el índice i = b −1 puede violar la propiedad heap. Sea j el índice del hijo más grande de a [ i ] (para un max-heap, o el hijo más pequeño para un min-heap) dentro del rango b , ..., e . (Si no existe tal índice porque 2 i > e entonces la propiedad heap se cumple para el rango recientemente extendido y no es necesario hacer nada). Al intercambiar los valores a [ i ] y a [ j ] se establece la propiedad heap para la posición i . En este punto, el único problema es que la propiedad heap podría no cumplirse para el índice j . La función sift-down se aplica de forma recursiva de cola al índice j hasta que se establezca la propiedad heap para todos los elementos.

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

En el caso de grandes montones y con memoria virtual , almacenar elementos en una matriz según 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 la cantidad de páginas a las que se accede hasta en un factor de diez. ^[12]

La operación de fusionar dos montones binarios requiere Θ( n ) para montones de igual tamaño. Lo mejor que puede hacer es (en caso de implementación de matriz) simplemente concatenar las dos matrices de montones y construir un montón del resultado. ^[13] Un montón de n elementos se puede fusionar con un montón de k elementos utilizando comparaciones de claves O(log n log k ) o, en caso de una implementación basada en punteros, en tiempo O(log n log k ). ^[14] En se presentó un algoritmo para dividir un montón de n elementos en dos montones de k y nk elementos, respectivamente, basado en una nueva vista de los montones como colecciones ordenadas de submontones. ^[15] 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 montón diferente, como los montones binomiales , que se pueden fusionar en O(log n ).

Además, se puede implementar un montón binario con una estructura de datos de árbol binario tradicional, pero existe un problema con la búsqueda del 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 "enhebrado" del á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 tanto del elemento más pequeño como del más grande en el tiempo. ^[16] Para ello, las filas se alternan entre el montón mínimo y el máximo. Los algoritmos son aproximadamente los mismos, pero, en cada paso, se deben considerar las filas alternadas con comparaciones alternadas. El rendimiento es aproximadamente el mismo que el de un montón normal de una sola dirección. Esta idea se puede generalizar a un montón mínimo-máximo-mediano. ${\displaystyle O}$ ${\displaystyle (\log n)}$

Derivación de ecuaciones de índice

En un montón basado en matrices, los hijos y el padre de un nodo se pueden ubicar mediante operaciones aritméticas simples en el índice del nodo. En esta sección se derivan 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, definimos el nivel de un nodo como su distancia desde la raíz, de modo que la raíz misma ocupa el nivel 0.

Nodos secundarios

Para un nodo general ubicado en el índice i (comenzando desde 0), primero derivaremos el índice de su hijo derecho, . ${\displaystyle {\text{right}}=2i+2}$

Sea el nodo i ubicado en el nivel L y observe que cualquier nivel l contiene exactamente nodos. Además, hay exactamente nodos contenidos en las capas hasta la capa l inclusive (piense en aritmética binaria; 0111...111 = 1000...000 - 1). Debido a que la raíz se almacena en 0, el k -ésimo nodo se almacenará en el índice . Al juntar estas observaciones se obtiene la siguiente expresión para el índice del último nodo en la capa l . ${\displaystyle 2^{l}}$ ${\displaystyle 2^{l+1}-1}$ ${\displaystyle (k-1)}$

${\displaystyle {\text{last}}(l)=(2^{l+1}-1)-1=2^{l+1}-2}$

Sea j nodos después del nodo i en la capa L, tales que

${\displaystyle {\begin{alignedat}{2}i=&\quad {\text{last}}(L)-j\\=&\quad (2^{L+1}-2)-j\\\end{alignedat}}}$

Cada uno de estos j nodos debe tener exactamente 2 hijos, por lo que debe haber nodos que separen al hijo derecho de i del final de su capa ( ). ${\displaystyle 2j}$ ${\displaystyle L+1}$

${\displaystyle {\begin{alignedat}{2}{\text{right}}=&\quad {\text{last(L + 1)}}-2j\\=&\quad (2^{L+2}-2)-2j\\=&\quad 2(2^{L+1}-2-j)+2\\=&\quad 2i+2\end{alignedat}}}$

Observando que el hijo izquierdo de cualquier nodo está siempre 1 lugar antes de su hijo derecho, obtenemos . ${\displaystyle {\text{left}}=2i+1}$

Si la raíz se encuentra en el índice 1 en lugar de 0, el último nodo de cada nivel se encuentra en el índice . Si se utiliza esto en todo el proceso, se obtiene y para los montículos con su raíz en 1. ${\displaystyle 2^{l+1}-1}$ ${\displaystyle {\text{left}}=2i}$ ${\displaystyle {\text{right}}=2i+1}$

Nodo padre

Cada nodo que no es raíz es el hijo izquierdo o derecho de su padre, por lo que debe cumplirse una de las siguientes condiciones:

• ${\displaystyle i=2\times ({\text{parent}})+1}$
• ${\displaystyle i=2\times ({\text{parent}})+2}$

Por eso,

${\displaystyle {\text{parent}}={\frac {i-1}{2}}\;{\textrm {or}}\;{\frac {i-2}{2}}}$

Consideremos ahora la expresión . ${\displaystyle \left\lfloor {\dfrac {i-1}{2}}\right\rfloor }$

Si el nodo es un hijo izquierdo, se obtiene el resultado inmediatamente; sin embargo, también se obtiene el resultado correcto si el nodo es un hijo derecho. En este caso, debe ser par y, por lo tanto, impar. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle (i-2)}$ ${\displaystyle (i-1)}$

${\displaystyle {\begin{alignedat}{2}\left\lfloor {\dfrac {i-1}{2}}\right\rfloor =&\quad \left\lfloor {\dfrac {i-2}{2}}+{\dfrac {1}{2}}\right\rfloor \\=&\quad {\frac {i-2}{2}}\\=&\quad {\text{parent}}\end{alignedat}}}$

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

${\displaystyle {\text{parent}}=\left\lfloor {\dfrac {i-1}{2}}\right\rfloor }$

Estructuras relacionadas

Dado que el orden de los hermanos en un montón no está especificado por la propiedad heap, los dos hijos de un solo nodo se pueden intercambiar libremente a menos que al hacerlo se viole la propiedad shape (comparar con treap ). Sin embargo, tenga en cuenta que en el montón común basado en matrices, simplemente intercambiar los hijos también podría requerir mover los nodos del subárbol de los hijos para conservar la propiedad heap.

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

Aquí se muestran las complejidades temporales ^[17] de varias estructuras de datos de montón. La abreviatura am. indica que la complejidad dada se amortiza, de lo contrario es una complejidad del peor caso. Para el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones suponen un montón mínimo.

1. De hecho, se puede demostrar que este procedimiento toma un tiempo Θ( n log n ) en el peor de los casos , lo que significa que n log n también es un límite inferior asintótico de la complejidad. ^{[1] : 167} Sin embargo, en el caso promedio (promedio de todas las permutaciones de n entradas), el método toma un tiempo lineal. ^[8]
2. Esto no significa que la clasificación se pueda realizar en tiempo lineal, ya que construir un montón es solo el primer paso del algoritmo de clasificación de montón .
3. make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar en Θ ( n ) tiempo siempre que meld se ejecute en O (log  n ) tiempo (donde ambas complejidades se pueden amortizar). ^{[18] [19]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[20]
4. Para los montículos persistentes (que no admiten decrease-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-min es la suma de los costos anteriores de delete-min y meld . ^[23] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-min todavía se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. ^[22]
5. Límite inferior de ^[26] límite superior de ^[27] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
6. Las colas de Brodal y los montículos de Fibonacci estrictos logran complejidades óptimas en el peor de los casos para los montículos. Primero se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que logra el mismo óptimo, excepto que no se admite la clave de disminución .

Referencias

1. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
2. Williams, JWJ (1964), "Algoritmo 232 - Heapsort", Comunicaciones de la ACM , 7 (6): 347–348, doi :10.1145/512274.512284
3. Y Narahari, "Montones binarios", Estructuras de datos y algoritmos
4. Porter, Thomas; Simon, Istvan (septiembre de 1975). "Inserción aleatoria en una estructura de cola de prioridad". IEEE Transactions on Software Engineering . SE-1 (3): 292–298. doi :10.1109/TSE.1975.6312854. ISSN  1939-3520. S2CID  18907513.
5. Mehlhorn, Kurt; Tsakalidis, A. (febrero de 1989). "Estructuras de datos". Universität des Saarlandes : 27. doi :10.22028/D291-26123. Porter y Simon [171] analizaron el coste medio de insertar un elemento aleatorio en un montón aleatorio en términos de intercambios. Demostraron que este promedio está limitado por la constante 1,61. Su prueba no se puede generalizar a secuencias de inserciones, ya que las inserciones aleatorias en montones aleatorios no crean montones aleatorios. El problema de inserción repetida fue resuelto por Bollobas y Simon [27]; muestran que el número esperado de intercambios está limitado por 1,7645. El coste en el peor de los casos de las inserciones y eliminaciones fue estudiado por Gonnet y Munro [84]; dan límites log log n + O(1) y log n + log n* + O(1) para el número de comparaciones respectivamente.
6. "python/cpython/heapq.py". GitHub . Consultado el 7 de agosto de 2020 .
7. "heapq — Algoritmo de cola de montón — Documentación de Python 3.8.5". docs.python.org . Consultado el 7 de agosto de 2020 . heapq.heappushpop(heap, item): inserta un elemento en el montón, luego extrae y devuelve el elemento más pequeño del montón. La acción combinada se ejecuta de manera más eficiente que heappush() seguida de una llamada separada a heappop().
8. Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
9. Suchenek, Marek A. (2012), "Análisis elemental pero preciso del peor caso del programa de construcción de pilas de Floyd", Fundamenta Informaticae , 120 (1): 75–92, doi :10.3233/FI-2012-751.
10. Doberkat, Ernst E. (mayo de 1984). "Análisis de caso promedio del algoritmo de Floyd para construir montones" (PDF) . Información y control . 6 (2): 114–131. doi : 10.1016/S0019-9958(84)80053-4 .
11. Pasanen, Tomi (noviembre de 1996). Análisis del caso de promedio elemental del algoritmo de Floyd para construir montones (informe técnico). Turku Centre for Computer Science. CiteSeerX 10.1.1.15.9526 . ISBN  951-650-888-X. Informe Técnico TUCS No. 64. Téngase en cuenta que este artículo utiliza la terminología original de Floyd, "siftup", para lo que ahora se denomina "sifting down " .
12. Kamp, Poul-Henning (11 de junio de 2010). "Lo estás haciendo mal". ACM Queue . Vol. 8, núm. 6.
13. Chris L. Kuszmaul. "binary heap" Archivado el 8 de agosto de 2008 en Wayback Machine . Dictionary of Algorithms and Data Structures, Paul E. Black, ed., Instituto Nacional de Estándares y Tecnología de EE. UU., 16 de noviembre de 2009.
14. J.-R. Sack y T. Strothotte "Un algoritmo para fusionar montones", Acta Informatica 22, 171-186 (1985).
15. Sack, Jörg-Rüdiger; Strothotte, Thomas (1990). "Una caracterización de los montículos y sus aplicaciones". Información y computación . 86 : 69–86. doi : 10.1016/0890-5401(90)90026-E .
16. Atkinson, MD; J.-R. Sack ; N. Santoro y T. Strothotte (1 de octubre de 1986). «Min-max heaps and generalized priority queues» (PDF) . Técnicas de programación y estructuras de datos. Comm. ACM, 29(10): 996–1000. Archivado desde el original (PDF) el 27 de enero de 2007. Consultado el 29 de abril de 2008 .
17. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. (1990). Introducción a los algoritmos (1.ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
18. Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables". Revista SIAM de informática . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
19. Tarjan, Robert (1983). "3.3. Montones de izquierdas". Estructuras de datos y algoritmos de red . págs. 38-42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
20. Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
21. "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
22. Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
23. Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
24. Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
25. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Apuntes de clase en informática, vol. 1851, Springer-Verlag, págs. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi :10.1007/3-540-44985-X_5, ISBN  3-540-67690-2
26. Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria Computacional . 46 (4): 473–501. doi :10.1145/320211.320214.
27. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . FOCS '05 Actas del 46.º Simposio anual IEEE sobre fundamentos de la informática. pp. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN.  0-7695-2468-0.
28. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485. doi :10.1137/100785351.
29. Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Revista de la Asociación de Maquinaria Computacional . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
30. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones de Fibonacci estrictos (PDF) . Actas del 44.º simposio sobre teoría de la computación - STOC '12. págs. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
31. Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52-58
32. Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341. ISBN 0-471-46983-1.

Enlaces externos

• Estructuras de datos abiertas - Sección 10.1 - BinaryHeap: un árbol binario implícito, Pat Morin
• Implementación del montón máximo binario en C por Robin Thomas
• Implementación del min heap binario en C por Robin Thomas