Montículo binomial

En informática , un montículo binomial es una estructura de datos que actúa como una cola de prioridad . Es un ejemplo de montículo fusionable (también llamado montículo combinable), ya que admite la fusión de dos montículos en tiempo logarítmico. Se implementa como un montículo similar a un montículo binario , pero utilizando una estructura de árbol especial que es diferente de los árboles binarios completos utilizados por los montículos binarios. ^{[ 1 ]} Los montículos binomiales fueron inventados en 1978 por Jean Vuillemin . ^{[ 1 ]}^{[ 2 ]}

Montículo binomial

Un montón binomial se implementa como un conjunto de árboles binomiales (compárese con un montón binario , que tiene la forma de un único árbol binario ), que se definen recursivamente de la siguiente manera: ^{[ 1 ]}

Un árbol binomial de orden 0 es un solo nodo.
Un árbol binomial de orden $k$ tiene un nodo raíz cuyos hijos son raíces de árboles binomiales de órdenes $k-1$ , $k-2$ , ..., 2, 1, 0 (en este orden).

Un árbol binomial de orden $k$ tiene $2^{k}$ nodos y altura $k$ . El nombre proviene de la forma: un árbol binomial de orden $k$ tiene ${\tbinom {k}{d}}$ nodos a profundidad $d$ , un coeficiente binomial . Debido a su estructura, un árbol binomial de orden $k$ se puede construir a partir de dos árboles de orden $k-1$ adjuntando uno de ellos como el hijo más a la izquierda de la raíz del otro árbol. Esta característica es fundamental para la operación de fusión de un montón binomial, que es su principal ventaja sobre otros montones convencionales. ^{[ 1 ]}^{[ 3 ]}

Estructura de un montón binomial

Un montón binomial se implementa como un conjunto de árboles binomiales que satisfacen las propiedades de un montón binomial : ^{[ 1 ]}

Cada árbol binomial en un montón obedece la propiedad de montón mínimo : la clave de un nodo es mayor o igual que la clave de su padre.
Puede haber como máximo un árbol binomial para cada orden, incluido el orden cero.

La primera propiedad garantiza que la raíz de cada árbol binomial contiene la clave más pequeña del árbol. Por consiguiente, la clave más pequeña de todo el montón es una de las raíces. ^{[ 1 ]}

La segunda propiedad implica que un montón binomial con $n$ los nodos constan de como máximo $1+\log _{2}n$ árboles binomiales, donde $\log _{2}$ es el logaritmo binario . El número y el orden de estos árboles están determinados de forma única por el número de nodos. $n$ : hay un árbol binomial para cada bit distinto de cero en la representación binaria del número $n$ . Por ejemplo, el número decimal 13 es 1101 en binario, $2^{3}+2^{2}+2^{0}$ y, por lo tanto, un montón binomial con 13 nodos constará de tres árboles binomiales de órdenes 3, 2 y 0 (véase la figura siguiente). ^{[ 1 ]}^{[ 3 ]}

Ejemplo de un montón binomial — Ejemplo de un montículo binomial que contiene 13 nodos con claves distintas. El montículo consta de tres árboles binomiales con órdenes 0, 2 y 3.

El número de formas diferentes que $n$ Los elementos con claves distintas se pueden organizar en un montón binomial igual al divisor impar más grande de $n!$ . Para $n=1,2,3,\dots$ estos números son

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (secuencia A049606 en el OEIS )

Si el $n$ Los elementos se insertan en un montón binomial en un orden aleatorio uniforme; cada una de estas disposiciones es igualmente probable. ^{[ 3 ]}

Implementación

Dado que ninguna operación requiere acceso aleatorio a los nodos raíz de los árboles binomiales, las raíces de estos árboles pueden almacenarse en una lista enlazada , ordenada según el orden ascendente del árbol. Debido a que el número de hijos de cada nodo es variable, no resulta conveniente que cada nodo tenga enlaces separados a cada uno de sus hijos, como sería común en un árbol binario ; en su lugar, es posible implementar este árbol utilizando enlaces desde cada nodo a su hijo de orden superior en el árbol y a su hermano del siguiente orden inferior. Estos punteros a hermanos pueden interpretarse como los punteros siguientes en una lista enlazada de los hijos de cada nodo, pero con el orden opuesto al de la lista enlazada de raíces: de mayor a menor orden, en lugar de al revés. Esta representación permite enlazar dos árboles del mismo orden, creando un árbol del siguiente orden superior, en tiempo constante. ^{[ 1 ]}^{[ 3 ]}

Unir

La operación de fusionar dos montículos se utiliza como subrutina en la mayoría de las demás operaciones. Una subrutina básica dentro de este procedimiento fusiona pares de árboles binomiales del mismo orden. Esto se puede hacer comparando las claves en las raíces de los dos árboles (las claves más pequeñas en ambos árboles). El nodo raíz con la clave mayor se convierte en hijo del nodo raíz con la clave menor, aumentando su orden en uno: ^{[ 1 ]}^{[ 3 ]}

función mergeTree(p, q) si p.root.key <= q.root.key devuelve p.addSubTree(q) de lo contrario devuelve q.addSubTree(p)

Para fusionar dos montones de forma más general, las listas de raíces de ambos montones se recorren simultáneamente de manera similar a la del algoritmo de fusión , en una secuencia desde órdenes de árboles más pequeños hasta órdenes más grandes. Cuando solo uno de los dos montones que se están fusionando contiene un árbol de orden $j$ , este árbol se mueve al montón de salida. Cuando ambos montones contienen un árbol de orden $j$ , los dos árboles se fusionan en un solo árbol de orden $j+1$ de modo que se satisfaga la propiedad de montón mínimo. Posteriormente puede ser necesario fusionar este árbol con algún otro árbol de orden $j+1$ en uno de los dos montones de entrada. En el transcurso del algoritmo, examinará como máximo tres árboles de cualquier orden, dos de los dos montones que fusionamos y uno compuesto por dos árboles más pequeños. ^{[ 1 ]}^{[ 3 ]}

función merge(p, q) mientras no (p.end() y q.end()) árbol = fusionarÁrbol(p.árbolactual(), q.árbolactual())

si no heap.currentTree().empty() árbol = fusionarÁrbol(árbol, montón.árbolactual())

 montón.agregarÁrbol(árbol) montón.next(); p.next(); q.next()

Dado que cada árbol binomial en un montón binomial corresponde a un bit en la representación binaria de su tamaño, existe una analogía entre la fusión de dos montones y la suma binaria de los tamaños de ambos, de derecha a izquierda. Siempre que se produce un acarreo durante la suma, esto corresponde a la fusión de dos árboles binomiales. ^{[ 1 ]}^{[ 3 ]}

El recorrido de cada árbol binomial durante la fusión solo involucra las raíces, por lo tanto, hace que el tiempo tomado como máximo sea de orden $\log _{2}n$ y por lo tanto el tiempo de ejecución es $O(\log n)$ . ^{[ 1 ]}^{[ 3 ]}

Insertar

Insertar un nuevo elemento en un montón se puede hacer simplemente creando un nuevo montón que contenga solo este elemento y luego fusionándolo con el montón original. Debido a la fusión, una sola inserción lleva tiempo. $O(\log n)$ Sin embargo, esto se puede acelerar utilizando un procedimiento de fusión que acorta la fusión después de que llega a un punto en el que solo uno de los montones fusionados tiene árboles de mayor orden. Con esta aceleración, a través de una serie de $k$ inserciones consecutivas, el tiempo total para las inserciones es $O(k+\log n)$ . Otra forma de expresar esto es que (después de la sobrecarga logarítmica para la primera inserción en una secuencia) cada inserción sucesiva tiene un tiempo amortizado de $O(1)$ (es decir, constante) por inserción. ^{[ 1 ]}^{[ 3 ]}

Una variante del montón binomial, el montón binomial asimétrico , logra un tiempo de inserción constante en el peor de los casos al utilizar bosques cuyos tamaños de árbol se basan en el sistema de numeración binario asimétrico en lugar del sistema de numeración binario. ^{[ 4 ]}

Encuentra el mínimo

Para encontrar el elemento mínimo del montón, encuentre el mínimo entre las raíces de los árboles binomiales. Esto se puede hacer en $O(\log n)$ tiempo, ya que solo hay $O(\log n)$ raíces de árboles para examinar. ^{[ 1 ]}

Al utilizar un puntero al árbol binomial que contiene el elemento mínimo, el tiempo para esta operación se puede reducir a $O(1)$ . El puntero debe actualizarse al realizar cualquier operación que no sea encontrar el mínimo. Esto se puede hacer en $O(\log n)$ tiempo por actualización, sin aumentar el tiempo de ejecución asintótico general de ninguna operación.

Eliminar mínimo

Para eliminar el elemento mínimo del montón, primero encuentre este elemento, retírelo de la raíz de su árbol binomial y obtenga una lista de sus subárboles hijos (cada uno de los cuales es un árbol binomial de distinto orden). Transforme esta lista de subárboles en un montón binomial separado reordenándolos de menor a mayor. Luego, combine este montón con el montón original. Dado que cada raíz tiene como máximo $\log _{2}n$ niños, crear este nuevo montón lleva tiempo $O(\log n)$ La fusión de montones lleva tiempo. $O(\log n)$ , por lo que toda la operación de eliminación mínima lleva tiempo $O(\log n)$ . ^{[ 1 ]}

función deleteMin(montón) min = heap.trees().first() para cada current en heap.trees() si current.root < min.root entonces min = current para cada árbol en min.subTrees() tmp.addTree(árbol) montón.eliminarÁrbol(min) fusionar(montón, tmp)

Disminuir la clave

Después de disminuir la clave de un elemento, este puede volverse menor que la clave de su padre, violando la propiedad de montón mínimo. Si este es el caso, intercambie el elemento con su padre, y posiblemente también con su abuelo, y así sucesivamente, hasta que la propiedad de montón mínimo ya no se viole. Cada árbol binomial tiene una altura como máximo $\log _{2}n$ , así que esto toma $O(\log n)$ tiempo. ^{[ 1 ]} Sin embargo, esta operación requiere que la representación del árbol incluya punteros de cada nodo a su padre en el árbol, lo que complica un poco la implementación de otras operaciones. ^{[ 3 ]}

Borrar

Para eliminar un elemento del montón, disminuya su clave a menos infinito (o, equivalentemente, a algún valor menor que cualquier elemento en el montón) y luego elimine el mínimo en el montón. ^{[ 1 ]}

Resumen de los tiempos de carrera

Aquí se muestran las complejidades temporales ^{[ 5 ]} de diversas estructuras de datos de montículo. La abreviatura am. indica que la complejidad dada está amortizada; de lo contrario, se trata de la complejidad en el peor de los casos. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones presuponen un montículo mínimo.

↑ make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar entiempo Θ ( n ) siempre que meld se ejecute en tiempo O (log n ) (donde ambas complejidades se pueden amortizar).^[⁶^]^[⁷^] Otro algoritmo alcanza Θ ( n ) para montones binarios.^[⁸^]
1 2 3 Paramontí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 antiguos de delete-min y meld .^{[ 11 ]} Aquí, hace que meld se ejecute en tiempo Θ (1) (amortizado, si el costo de insert es) mientras que delete-min todavía se ejecuta en O (log n ). Aplicado a montículos binomiales asimétricos, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos.^[¹⁰^]
↑ Límite inferior de $\Omega (\log \log n),$ ^{[ 14 ]} límite superior de $O(2^{2{\sqrt {\log \log n}}}).$ ^{[ 15 ]}
Las colas de Brodal y los montículos de Fibonacci estrictos alcanzan complejidades óptimas en el peor de los casos para los montículos. Inicialmente se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que alcanza el mismo óptimo, excepto queno admite la decreción de clave .

Aplicaciones

Véase también

Montículo débil , una combinación de las estructuras de datos de montículo binario y montículo binomial.

Referencias

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest , Ronald L. ; Stein, Clifford (2001) [1990]. "Capítulo 19: Montículos binomiales". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 455–475 . ISBN 0-262-03293-7.
↑ Vuillemin, Jean (1 de abril de 1978). "Una estructura de datos para manipular colas de prioridad" . Communications of the ACM . 21 (4): 309– 315. doi : 10.1145/359460.359478 .
1 2 3 4 5 6 7 8 9 10 Brown, Mark R. (1978). "Implementación y análisis de algoritmos de cola binomial". SIAM Journal on Computing . 7 (3): 298– 319. doi : 10.1137/0207026 . MR 0483830 .
↑ 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
1 2 3 4 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.
1 2 3 Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montículos autoajustables" . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .
1 2 Tarjan, Robert (1983). "3.3. Montones izquierdistas". Estructuras de datos y algoritmos de red . págs. 38–42 . doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5.
↑ Hayward, Ryan; McDiarmid, Colin (1991). "Análisis del caso promedio de la 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 del original (PDF) el 5 de febrero de 2016. Recuperado el 28 de enero de 2016 .
↑ "Montículo binomial | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 30 de septiembre de 2019 .
1 2 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
↑ Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). págs. 158–162 . ISBN 9780521631242.
↑ Takaoka, Tadao (1999), Teoría de los montículos 2-3 (PDF) , pág. 12
↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77 , arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2
↑ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de los montículos de emparejamiento y estructuras de datos relacionadas" (PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
↑ Pettie, Seth (2005). Hacia un análisis final de los montículos de emparejamiento (PDF) . Actas de FOCS '05 del 46.º Simposio Anual 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.
↑ 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 .
↑ Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 .
↑ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montículos 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.
↑ 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
↑ 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

Dos implementaciones en C de un montículo binomial (una genérica y otra optimizada para claves enteras).
Implementación en Haskell de un montón binomial
Implementación en Common Lisp de un montón binomial

[9] make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar entiempo Θ ( n ) siempre que meld se ejecute en tiempo O (log n ) (donde ambas complejidades se pueden amortizar).^[⁶^]^[⁷^] Otro algoritmo alcanza Θ ( n ) para montones binarios.^[⁸^]

[bootstrap-meld-11] 1 2 3 Paramontí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 antiguos de delete-min y meld .^{[ 11 ]} Aquí, hace que meld se ejecute en tiempo Θ (1) (amortizado, si el costo de insert es) mientras que delete-min todavía se ejecuta en O (log n ). Aplicado a montículos binomiales asimétricos, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos.^[¹⁰^]

[pairingdecreasekey-18] Límite inferior de $\Omega (\log \log n),$ ^{[ 14 ]} límite superior de $O(2^{2{\sqrt {\log \log n}}}).$ ^{[ 15 ]}

[optimum-22] Las colas de Brodal y los montículos de Fibonacci estrictos alcanzan complejidades óptimas en el peor de los casos para los montículos. Inicialmente se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que alcanza el mismo óptimo, excepto queno admite la decreción de clave .

[clrs-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest , Ronald L. ; Stein, Clifford (2001) [1990]. "Capítulo 19: Montículos binomiales". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 455–475 . ISBN 0-262-03293-7.

[2] Vuillemin, Jean (1 de abril de 1978). "Una estructura de datos para manipular colas de prioridad" . Communications of the ACM . 21 (4): 309– 315. doi : 10.1145/359460.359478 .

[brown-3] 1 2 3 4 5 6 7 8 9 10 Brown, Mark R. (1978). "Implementación y análisis de algoritmos de cola binomial". SIAM Journal on Computing . 7 (3): 298– 319. doi : 10.1137/0207026 . MR 0483830 .

[4] 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

[CLRS-5] 1 2 3 4 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.

[sleator-tarjan-skew-6] 1 2 3 Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montículos autoajustables" . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .

[tarjan-leftist-7] 1 2 Tarjan, Robert (1983). "3.3. Montones izquierdistas". Estructuras de datos y algoritmos de red . págs. 38–42 . doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5.

[hayward-mcdiarmid-heap-build-8] Hayward, Ryan; McDiarmid, Colin (1991). "Análisis del caso promedio de la 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 del original (PDF) el 5 de febrero de 2016. Recuperado el 28 de enero de 2016 .

[10] "Montículo binomial | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 30 de septiembre de 2019 .

[brodal-okasaki-12] 1 2 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

[13] Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). págs. 158–162 . ISBN 9780521631242.

[14] Takaoka, Tadao (1999), Teoría de los montículos 2-3 (PDF) , pág. 12

[Iacono-15] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77 , arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2

[Fredman1999-16] Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de los montículos de emparejamiento y estructuras de datos relacionadas" (PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .

[17] Pettie, Seth (2005). Hacia un análisis final de los montículos de emparejamiento (PDF) . Actas de FOCS '05 del 46.º Simposio Anual 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.

[19] 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 .

[Fredman_And_Tarjan-20] Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montículos de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 .

[21] Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montículos 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.

[23] 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

[24] 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.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[

[

[ 11 ]

[

[ 14 ]

[ 15 ]