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]
Montón binario (min) | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol binario / montón | ||||||||||||||||||||||||
Inventado | 1964 | ||||||||||||||||||||||||
Inventado por | JWJ Williams | ||||||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||||||
|
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 en los hijos del nodo, de acuerdo con algún orden total .
Los montones donde la clave principal es mayor o igual que (≥) las claves secundarias se denominan max-heaps ; aquellos en los que es menor o igual a (≤) se denominan min-montones . Los algoritmos eficientes ( tiempo logarítmico ) son conocidos por 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 de 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 las relaciones hijo-padre .
Operaciones de montón
Tanto las operaciones de inserción como de eliminación modifican el montón para que se ajuste a la propiedad de forma primero, agregando o quitando del 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 O (log n ).
Insertar
Para agregar un elemento a un montón, podemos realizar este algoritmo:
- Agregue el elemento al nivel inferior del montón en el espacio abierto más a la izquierda.
- Compare el elemento agregado con su padre; si están en el orden correcto, deténgase.
- Si no es así, 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 up-heap (también conocida como bubble-up , percolate-up , sift-up , trickle-up , swim- up , heapify-up o en cascada ).
El número de operaciones requeridas depende solo del número de niveles que el nuevo elemento debe elevarse para satisfacer la propiedad del montón. Por 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). [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 desde 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 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 ).
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) mientras se retiene la propiedad del montón es el siguiente:
- Reemplace la raíz del montón con el último elemento del último nivel.
- Compare la nueva raíz con sus hijos; si están en el orden correcto, deténgase.
- De lo 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 su hijo más grande en un montón máximo).
Los pasos 2 y 3, que restauran la propiedad de la pila comparando y posiblemente intercambiando un nodo con uno de sus hijos, se denominan pila descendente (también conocida como burbuja descendente , filtración descendente , cribado descendente , hundimiento descendente , goteo down , heapify-down , cascade-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 con 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 elementos más:
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 A respaldado por una matriz de longitud ( A ). Tenga en cuenta que A está indexado a partir de 1.
// Realice una operación de pila baja o de pila baja para un montón máximo// A : una matriz que representa el montón, indexada a partir de 1// i : el índice en el que comenzar cuando se apila 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 es más grande ≠ i entonces : intercambia A [ i ] y A [ más grande ] Max-Heapify ( A , más grande )
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 pueden violar la propiedad del montón. La operación de almacenamiento descendente (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 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 (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 tanto ascendente como descendente. En su lugar, podemos hacer solo una operación de descarga, de la siguiente manera:
- Compare si el elemento que estamos empujando o la parte superior del montón es mayor (asumiendo un montón máximo)
- Si la raíz del montón es mayor:
- Reemplazar la raíz con el nuevo elemento
- Down-heapify comenzando desde la raíz
- De lo contrario, devuelva 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. [6] [7] Se supone que la matriz de pila tiene su primer elemento en el índice 1.
// Empuje un nuevo elemento a un montón (máximo) y luego extraiga la raíz del montón resultante. // montón : una matriz que representa el montón, indexada en 1// item : un elemento para insertar// Devuelve el mayor de los dos entre el elemento y la raíz del montón .Push-Pop ( heap : List, artículo : T) -> T: si montón no está vacío y heap [1]> elemento continuación : //de intercambio montón [1] y artículo _downheap ( montón de partida del índice 1) artículo devuelto
Se puede definir una función similar para hacer estallar 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// item : un elemento para insertar// Devuelve la raíz actual del montón Reemplazar ( montón : Lista, elemento : T) -> T: intercambio de montón [1] y elemento _downheap ( montón a partir del índice 1) return item
Buscar
Encontrar un elemento arbitrario lleva O (n) tiempo.
Borrar
La eliminación de un elemento arbitrario se puede hacer de la siguiente manera:
- Encuentra el índice del elemento que queremos eliminar
- Intercambia este elemento con el último elemento
- Bajar o aumentar la pila para restaurar la propiedad del montón. En un max-heap (min-heap), up-heapify solo se requiere cuando la nueva clave del elementoes mayor (menor) que el anterior porque solo se puede violar la propiedad de pila del elemento padre. Suponiendo que la propiedad del montón era válida entre el elementoy sus hijos antes del intercambio de elementos, no puede ser violado 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 un almacenamiento descendente porque la propiedad del almacenamiento dinámico solo se puede violar en los elementos secundarios.
Disminuir o aumentar la clave
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 realizar una acumulación descendente o una acumulación ascendente para restaurar la propiedad del montón.
La tecla de disminución se puede hacer de la siguiente manera:
- Encuentra el índice del elemento que queremos modificar
- Disminuir el valor del nodo
- Down-heapify (asumiendo un montón máximo) para restaurar la propiedad del montón
La tecla de aumento se puede hacer de la siguiente manera:
- Encuentra el índice del elemento que queremos modificar
- Incrementar el valor del nodo
- 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. Este enfoque, llamado método de Williams en honor al inventor de los montones binarios, se ve fácilmente que se ejecuta en un 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 la 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, tamice la raíz de cada subárbol hacia abajo como en el algoritmo de eliminación hasta que se restaure la propiedad del montón. Más específicamente si todos los subárboles que comienzan a cierta altura ya han sido "apilados" (el nivel más bajo correspondiente a ), los árboles en altura se puede acumular enviando su raíz a lo largo de la ruta de los niños de valor máximo cuando se construye un montón máximo, o los niños de valor mínimo cuando se construye un montón mínimo. Este proceso llevaoperaciones (swaps) por nodo. En este método, la mayor parte de la acumulación tiene lugar en los niveles inferiores. Dado que la altura del montón es, el número de nodos en altura es . Por lo tanto, el costo de apilar todos los subárboles es:
Esto usa el hecho de que la serie infinita dada converge .
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:
donde s 2 ( n ) es la suma de todos los dígitos de la representación binaria de n y e 2 ( 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 2 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 (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 hojas para el árbol (asumiendo que los índices comienzan en 1), por lo que cada uno es un elemento montón, y no es necesario reducirlo. Build-Max-Heap ejecuta Max-Heapify en cada uno de los nodos del árbol restantes.
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
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 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 de montón un ejemplo simple de una estructura de datos implícita o una lista de Ahnentafel . Los detalles dependen de la posición de la raíz, que a su vez puede depender de las limitaciones de un lenguaje de programación utilizado para la implementación o de las preferencias 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 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 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 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 usa en el algoritmo de clasificación de pila , donde permite que el espacio en la matriz de entrada se reutilice para almacenar la pila (es decir, el algoritmo se realiza en el lugar ). La implementación también es útil para usar como una cola de prioridad donde el uso de una matriz dinámica permite 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 sift-down 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 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 montón vale para las necesidades de rango y nada recién extendidos por hacer.) Por el intercambio de los valores de una [ i ] y una [ j ] la propiedad montón para la posición i está establecida . 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 sift-down se aplica de forma recursiva al índice j hasta que se establezca la propiedad del montón para todos los elementos.
La función de tamizado es rápida. En cada paso solo necesita dos comparaciones y un intercambio. El valor del índice en el que está funcionando se duplica en cada iteración, por lo que se requieren pasos de log 2 e como máximo .
Para grandes montones y el uso de 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 B-heaps son montones binarios que mantienen subárboles en una sola página, reduciendo 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 de igual tamaño. Lo mejor que puede hacer es (en el caso de la implementación de una 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] Se presentó un algoritmo para dividir un montón en n elementos en dos montones en k y nk elementos, respectivamente, basado en una nueva vista de montones como colecciones ordenadas de submontes. [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 para encontrar el elemento adyacente en el último nivel del montón binario al agregar un elemento. Este elemento puede determinarse mediante algoritmos o mediante la adición de datos adicionales a los nodos, llamados "threading" el árbol, en lugar de simplemente almacenar referencias a los niños, almacenamos el finde sucesor del nodo también.
Es posible modificar la estructura del montón para permitir la extracción del elemento más pequeño y más grande en O {\ Displaystyle O} hora. [16] Para hacer esto, las filas alternan entre min heap y max-heap. Los algoritmos son aproximadamente 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.
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 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, definiremos el nivel de un nodo como su distancia desde la raíz, de modo que la raíz misma ocupe el nivel 0.
Nodos secundarios
Para un nodo general ubicado en el índice (comenzando desde 0), primero derivaremos el índice de su hijo derecho, .
Deja que el nodo estar ubicado en el nivel , y tenga en cuenta que cualquier nivel contiene exactamente nodos. Además, hay exactamente nodos contenidos en las capas hasta la capa incluida (piense en aritmética binaria; 0111 ... 111 = 1000 ... 000 - 1). Debido a que la raíz se almacena en 0, laEl 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 .
Dejalo ser nodos tras nodo en la capa L, de modo que
Cada uno de estos los nodos deben tener exactamente 2 hijos, por lo que debe haber nodos que se separan hijo de la derecha desde el final de su capa ().
Según sea necesario.
Teniendo en cuenta que el hijo izquierdo de cualquier nodo siempre está 1 lugar antes que su hijo derecho, obtenemos .
Si la raíz se encuentra en el índice 1 en lugar de 0, el último nodo de cada nivel está en su lugar en el índice . Usando esto en todos los rendimientos y para montones con su raíz en 1.
Nodo padre
Cada nodo es el hijo izquierdo o derecho de su padre, por lo que sabemos que cualquiera de los siguientes es cierto.
Por eso,
Ahora considere la expresión .
Si nodo es un hijo izquierdo, esto da el resultado inmediatamente, sin embargo, también da el resultado correcto si el nodo es un niño adecuado. En este caso, debe ser parejo, y por lo tanto debe ser extraño.
Por lo tanto, independientemente de si un nodo es un hijo izquierdo o derecho, su padre se puede encontrar mediante la expresión:
Estructuras relacionadas
Dado que el orden de los hermanos en un montón no está especificado por la propiedad del montón, los dos hijos de un solo nodo se pueden intercambiar libremente a menos que al hacerlo se viole la propiedad de la 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 puede 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 tiempos de ejecución
Aquí están las complejidades de tiempo [17] de varias estructuras de datos de pila. Los nombres de funciones asumen un min-heap. Para el significado de " O ( f )" y " Θ ( f )" ver Big O notación .
Operación | find-min | eliminar min | insertar | tecla de disminución | fusionar |
---|---|---|---|---|---|
Binario [17] | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
Izquierdista | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
Binomio [17] [18] | Θ (1) | Θ (log n ) | Θ (1) [c] | Θ (log n ) | O (log n ) [d] |
Fibonacci [17] [19] | Θ (1) | O (log n ) [c] | Θ (1) | Θ (1) [c] | Θ (1) |
Emparejamiento [20] | Θ (1) | O (log n ) [c] | Θ (1) | o (log n ) [c] [e] | Θ (1) |
Brodal [23] [f] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
Emparejamiento de rango [25] | Θ (1) | O (log n ) [c] | Θ (1) | Θ (1) [c] | Θ (1) |
Fibonacci estricto [26] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
2-3 montón [27] | O (log n ) | O (log n ) [c] | O (log n ) [c] | Θ (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 en la complejidad. [1] : 167 En el caso promedio (promediando todas las permutaciones de n entradas), sin embargo, el método toma un tiempo lineal. [8]
- ^ Esto no quiere decir que la clasificación se puede hacer en un tiempo lineal desde la construcción de un montón es sólo el primer paso de la heapsort algoritmo.
- ^ a b c d e f g h i Tiempo amortizado.
- ^ n es el tamaño del montón más grande.
- ^ Límite inferior de[21] límite superior de[22]
- ^ Brodal y Okasaki describen más tarde unavariante persistente con los mismos límites, excepto para la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). [24]
Ver también
- Montón
- Heapsort
Referencias
- ↑ a b 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.
- ^ Williams, JWJ (1964), "Algorithm 232 - Heapsort", Communications of the ACM , 7 (6): 347–348, doi : 10.1145 / 512274.512284
- ^ eEL, CSA_Dept, IISc, Bangalore, "Binary Heaps" , estructuras de datos y algoritmosMantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Porter, Thomas; Simon, Istvan (septiembre de 1975). "Inserción aleatoria en una estructura de cola de prioridad". Transacciones IEEE sobre ingeniería de software . SE-1 (3): 292-298. doi : 10.1109 / TSE.1975.6312854 . ISSN 1939-3520 . S2CID 18907513 .
- ^ Mehlhorn, Kurt; Tsakalidis, A. (febrero de 1989). "Estructuras de datos" : 27.
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. Sus documentos de prueba no se generalizan 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 costo del peor caso de inserciones y eliminaciones; dan los límites log log n + O (1) y log n + log n * + O (1) para el número de comparaciones, respectivamente.
Cite journal requiere|journal=
( ayuda ) - ^ "python / cpython / heapq.py" . GitHub . Consultado el 7 de agosto de 2020 .
- ^ "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): Empuje el elemento en el montón, luego haga estallar y devuelva 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 ().
- ^ a b Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de la construcción de montón por 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 .
- ^ Suchenek, Marek A. (2012), "Análisis elemental pero preciso del peor de los casos del programa de construcción de pilas de Floyd" , Fundamenta Informaticae , 120 (1): 75–92, doi : 10.3233 / FI-2012-751.
- ^ 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 .
- ^ Pasanen, Tomi (noviembre de 1996). Análisis de casos promedio elemental del algoritmo de Floyd para construir montones (informe técnico). Centro Turku de Ciencias de la Computación. CiteSeerX 10.1.1.15.9526 . ISBN 951-650-888-X. Informe técnico de TUCS No. 64.Tenga en cuenta que este trabajo se emplea terminología original "siftup" de Floyd por lo que ahora se llama tamizar abajo .
- ^ Kamp, Poul-Henning (11 de junio de 2010). "Lo estás haciendo mal" . Cola de ACM . Vol. 8 no. 6.
- ^ Chris L. Kuszmaul. "binary heap" Archivado el 8 de agosto de 2008 en la 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.
- ^ J.-R. Sack y T. Strothotte "An Algorithm for Merging Heaps" , Acta Informatica 22, 171-186 (1985).
- ^ Sack, 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 .
- ^ Atkinson, MD; J.-R. saco ; N. Santoro y T. Strothotte (1 de octubre de 1986). "Montones min-max y colas de prioridad generalizada" (PDF) . Técnicas de programación y estructuras de datos. Comm. ACM, 29 (10): 996–1000.
- ^ a b c d 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.
- ^ "Binomial Heap | Wiki brillante de matemáticas y ciencias" . shiny.org . Consultado el 30 de septiembre de 2019 .
- ^ Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados" (PDF) . Revista de la Asociación de Maquinaria Informática . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145 / 28869.28874 .
- ^ Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Lecture Notes in Computer Science, 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
- ^ 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 Informática . 46 (4): 473–501. doi : 10.1145 / 320211.320214 .
- ^ Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. págs. 174-183. CiteSeerX 10.1.1.549.471 . doi : 10.1109 / SFCS.2005.75 . ISBN 0-7695-2468-0.
- ^ 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
- ^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montón de abajo hacia arriba". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Computación . 40 (6): 1463–1485. doi : 10.1137 / 100785351 .
- ^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones estrictos de Fibonacci (PDF) . Actas del 44º simposio de 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.
- ^ Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , p. 12
enlaces externos
- Estructuras de datos abiertos - Sección 10.1 - BinaryHeap: un árbol binario implícito , Pat Morin
- Implementación de binary max heap en C por Robin Thomas
- Implementación de binary min heap en C por Robin Thomas