montón binario

Variante de 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 heapsort . ^[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), se llenan por completo 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 en los hijos del nodo, según algún orden total .

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 in situ 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 las relaciones entre padres e hijos. .

Operaciones de montón

Tanto la operación de inserción como la de eliminación modifican el montón para que se ajuste primero a la propiedad de forma, agregando o eliminando desde el 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 insertar un elemento a un montón, realizamos los siguientes pasos:

1. Agregue 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, detente.
3. De lo contrario, intercambie el elemento con su padre y regrese 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 de montón (también conocida como burbuja , filtración , tamizado , goteo , natación) . up , heapify-up , cascade-up o fix-up ).

El número de operaciones necesarias depende únicamente del número de niveles que debe subir el nuevo elemento 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 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 con el siguiente aspecto después del primer intercambio:

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

que es un montón máximo válido. No es necesario 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 , 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, detente.
3. De lo contrario, intercambie el elemento con uno de sus hijos y regrese al paso anterior. (Intercambie con su hijo más pequeño en un montón mínimo y 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 montón descendente (también conocido como burbuja descendente , filtración , tamizado , hundimiento , goteo). operación 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 sustituimos 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 ( A ) . A está indexado a partir de 1.

// Realizar una operación de reducción o reducción del montón para un montón máximo// A : una matriz que representa el montón, indexada a partir de 1// i : el índice para comenzar al acumular 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  mayor ≠ i  entonces : intercambiar  A [ i ] y A [ mayor ] Max-Heapify ( A , mayor )

Para que el algoritmo anterior vuelva a amontonar 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 reducción del montón (sin el intercambio anterior) también se puede utilizar 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 hijo 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 temporal relativa a la altura del árbol, u O(log 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 upheapy downheap. En cambio, podemos hacer solo una downheapoperación, de la siguiente manera:

1. Compare si el elemento que estamos empujando o la parte superior del montón que se asoma 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. Amontonar hacia abajo comenzando desde la raíz
3. De lo contrario, devuelva el artículo que estamos promocionando.

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

// Inserta un nuevo elemento en 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 a insertar// Devuelve el mayor de los dos entre el elemento y la raíz del montón . Push-Pop ( montón : Lista<T>, elemento : T) -> T: si  el montón no está vacío y el montón[1] > elemento  entonces : // < si el montón mínimo intercambia  el montón [1] y el elemento _downheap( inicio del montón del índice 1) devolver  artículo

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 a insertar// Devuelve la raíz actual del montón Reemplazar ( montón : Lista<T>, elemento : T) -> T: intercambiar  montón [1] y elemento _downheap( montón a partir del índice 1) devolver  elemento

Buscar

Encontrar un elemento arbitrario lleva 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 (montón mínimo), up-heapify solo se requiere cuando la nueva clave del elemento es mayor (menor) que la anterior porque solo se puede violar la propiedad del montón del elemento principal. 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 más grande (más pequeño). Cuando la nueva clave es menor (mayor) que la anterior, solo se requiere una reducción del montón porque la propiedad del montón solo podría violarse en los elementos secundarios. ${\displaystyle i}$ ${\displaystyle i}$

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 reducir o aumentar el almacenamiento para restaurar la propiedad del montón.

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

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

La clave de aumento se puede hacer 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

Se puede construir un montón a partir de una matriz de n elementos de entrada comenzando con un montón vacío y luego insertando sucesivamente cada elemento. Se ve fácilmente que este enfoque, llamado método de Williams en honor al inventor de los montones binarios, se ejecuta 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 representarse mediante una matriz, ver más abajo). Luego, comenzando desde el nivel más bajo y avanzando hacia arriba, tamice 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 que comienzan en cierta altura ya han sido "amontonados" (el nivel más bajo correspondiente a ), los árboles en altura se pueden amontonar enviando su raíz hacia abajo a lo largo del camino de los hijos con valor máximo al construir un montón máximo, o niños con valor mínimo al construir un montón mínimo. Este proceso requiere operaciones (intercambios) por nodo. En este método la mayor parte de la amontonación tiene lugar en los niveles inferiores. Como la altura del montón es , el número de nodos en la altura es . Por tanto, el coste 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 acerca 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 usando repetidamente Max-Heapify (hacia abajo 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 (asumiendo que los índices comienzan en 1); por lo tanto, cada uno es un elemento. montón, y no es necesario reducirlo. 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 haga:  Max-Heapify ( A , i )

Implementación del 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 montones se implementan comúnmente con una matriz . Cualquier árbol binario se puede almacenar en una matriz, pero como un montón binario es siempre un árbol binario completo, se puede almacenar de forma compacta. No se requiere espacio para los punteros ; en cambio, el padre y los hijos de cada nodo se pueden encontrar mediante aritmética en índices de matriz. Estas propiedades hacen de esta implementación del montón un ejemplo simple de una estructura de datos implícita o lista de Ahnentafel . Los detalles dependen de la posición de la raíz, que a su vez puede depender de las limitaciones del lenguaje de programación utilizado para la implementación o de las preferencias del programador. En concreto, a veces la raíz se sitúa 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 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 del 0 al n − 1, entonces cada elemento a en el índice i tiene

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

Esta implementación se utiliza 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 in situ ). 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 upheapo downheapse pueden expresar en términos de una matriz de la siguiente manera: supongamos que la propiedad del montón se cumple para los índices b , b +1, ..., e . La función de filtrado extiende la propiedad del montón a b −1, b , b +1, ..., e . Sólo el índice i = b −1 puede violar la propiedad del montón. Sea j el índice del hijo más grande de a [ i ] (para un montón máximo, o el hijo más pequeño para un montón mínimo) dentro del rango b , ..., e . (Si no existe tal índice porque 2 i > e entonces la propiedad del montón se mantiene para el rango recién extendido y no es necesario hacer nada). Al intercambiar los valores a [ i ] y a [ j ], se establece la propiedad del montón para la posición i . En este punto, el único problema es que es posible que la propiedad del montón no se cumpla para el índice j . La función de filtrado se aplica de forma recursiva al índice j hasta que se establece la propiedad del montón para todos los elementos.

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

Para grandes montones y que utilizan 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. ^[12]

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 una implementación de matriz) simplemente concatenar las dos matrices del montón y crear un montón del resultado. ^[13] Un montón de n elementos se puede fusionar con un montón de k elementos usando comparaciones de claves O(log n log k ) o, en el 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 visión de los montones como colecciones ordenadas de submontones. ^[15] El algoritmo requiere O(log n * log n ) comparaciones. 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 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 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 "enhebrar" 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 más grande en el tiempo. ^[16] Para hacer esto, las filas alternan entre montón mínimo y montón máximo. Los algoritmos son más o menos los mismos, pero, en cada paso, se deben considerar las filas alternas con comparaciones alternas. 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 los padres de un nodo se pueden ubicar mediante aritmética simple en el índice del nodo. Esta sección deriva las ecuaciones relevantes para montones con su raíz en el índice 0, con notas adicionales sobre 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}$

Supongamos que el nodo i esté ubicado en el nivel L y tenga en cuenta que cualquier nivel l contiene exactamente nodos. Además, hay exactamente nodos contenidos en las capas hasta la capa l inclusive (piense en la 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}$

Sean 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 nodos j 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}}}$

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

Si la raíz está ubicada en el índice 1 en lugar de 0, el último nodo de cada nivel está en el índice . Usar esto en todos los rendimientos y en montones con su raíz en 1. ${\displaystyle 2^{l+1}-1}$ ${\displaystyle {\text{left}}=2i}$ ${\displaystyle {\text{right}}=2i+1}$

Nodo padre

Cada nodo no raíz es hijo izquierdo o derecho de su padre, por lo que debe cumplirse uno de los siguientes:

• ${\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, esto da el resultado inmediatamente; sin embargo, también da el resultado correcto si el nodo es un hijo derecho. En este caso, debe ser par y, por tanto, debe ser 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 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 al hacerlo se viole la propiedad de forma (compárese con treap ). Sin embargo, tenga en cuenta que en el montón común basado en matrices, el simple hecho de intercambiar los elementos secundarios también podría requerir mover los nodos del subárbol de los elementos secundarios 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 tiempos de ejecución

A continuación se presentan las complejidades temporales ^[17] de varias estructuras de datos del montón. Los nombres de las funciones suponen un montón mínimo. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación O grande .

1. De hecho, se puede demostrar que este procedimiento toma Θ ( n log n ) tiempo 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 (promediando 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. Tiempo amortizado.
4. Brodal y Okasaki describen una técnica para reducir la complejidad de fusión en el peor de los casos a Θ (1); esta técnica se aplica a cualquier estructura de datos de montón que tenga inserción en Θ (1) y find-min , delete-min , fusione en O (log  n ).
5. Límite inferior de ^[21] límite superior de ^[22] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
6. Brodal y Okasaki describen más tarde una variante persistente con los mismos límites excepto la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). ^[27]

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", Algoritmos y estructuras de datos
4. Portero, Thomas; Simon, Istvan (septiembre de 1975). "Inserción aleatoria en una estructura de cola prioritaria". Transacciones IEEE sobre ingeniería de software . 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 costo promedio de insertar un elemento aleatorio en un montón aleatorio en términos de intercambios. Demostraron que este promedio está acotado por la constante 1,61. Su prueba no se generaliza a secuencias de inserciones, ya que las inserciones aleatorias en montones aleatorios no crean montones aleatorios. El problema de la inserción repetida fue resuelto por Bollobas y Simon [27]; muestran que el número esperado de intercambios está limitado por 1,7645. Gonnet y Munro [84] estudiaron el peor coste de las inserciones y eliminaciones; 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(montón, elemento): inserta el elemento en el montón, luego saca 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 creación de montón mediante inserción repetida" (PDF) . J. Algoritmos . 12 : 126-153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 5 de febrero de 2016 . Consultado el 28 de enero de 2016 . 
9. Suchenek, Marek A. (2012), "Análisis elemental pero preciso del peor de los casos del programa de construcción en pilas de Floyd", Fundamenta Informaticae , 120 (1): 75–92, doi :10.3233/FI-2012-751.
10. Doberkat, Ernst E. (mayo de 1984). "Un 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 de caso promedio elemental del algoritmo de Floyd para construir montones (Reporte técnico). Centro de Ciencias de la Computación de Turku. CiteSeerX 10.1.1.15.9526 . ISBN  951-650-888-X. Informe Técnico TUCS No. 64. Tenga en cuenta que este artículo utiliza la terminología original de Floyd "siftup" para lo que ahora se llama sifting down .
12. Kamp, Poul-Henning (11 de junio de 2010). "Lo estás haciendo mal". Cola ACM . vol. 8, núm. 6.
13. Chris L. Kuszmaul. "montón binario" Archivado el 8 de agosto de 2008 en Wayback Machine . Diccionario de algoritmos y estructuras de datos, 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. Saco, Jörg-Rüdiger; Strothotte, Thomas (1990). "Una caracterización de los montones y sus aplicaciones". Información y Computación . 86 : 69–86. doi : 10.1016/0890-5401(90)90026-E .
16. Atkinson, médico; J.-R. Bolsa ; N. Santoro y T. Strothotte (1 de octubre de 1986). "Montones mínimos y máximos y colas de prioridad generalizada" (PDF) . Técnicas de programación y estructuras de datos. Com. 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. "Montón binomial | Wiki brillante de matemáticas y ciencias". brillante.org . Consultado el 30 de septiembre de 2019 .
19. 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
20. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Apuntes de conferencias sobre 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
21. Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia del emparejamiento de montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria de Computación . 46 (4): 473–501. doi :10.1145/320211.320214.
22. Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Actas del 46º Simposio anual del IEEE sobre fundamentos de la informática. págs. 174-183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN  0-7695-2468-0.
23. 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.
24. 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 de Computación . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
25. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones estrictos de Fibonacci (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.
26. Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Proc. Séptimo Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52–58
27. Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montón ascendente". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.
28. Takaoka, Tadao (1999), Teoría de 2 a 3 montones (PDF) , p. 12

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 montón mínimo binario en C por Robin Thomas