Hispanopedia Wiki
Articulo de referencia

Montón binario

Ejemplo de un montículo 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...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo de un montículo 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 implementar el ordenamiento por montones . [ 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 de montón: la clave almacenada en cada nodo es mayor o igual que (≥) (o menor o igual que (≤)) las claves en los hijos del nodo, según algún orden total .

Los montículos donde la clave padre es mayor o igual que (≥) las claves hijas se denominan montículos máximos ; aquellos donde es menor o igual que (≤) se denominan montículos mínimos . Se conocen algoritmos eficientes (es decir, de tiempo logarítmico ) para las dos operaciones necesarias para implementar una cola de prioridad en un montículo binario:

  • Insertar un elemento;
  • Eliminar el elemento más pequeño o más grande de un montón mínimo o máximo (respectivamente).

Los montículos binarios también se emplean comúnmente en el algoritmo de ordenación por montículos , que es un algoritmo in situ, ya que los montículos binarios se pueden implementar como una estructura de datos implícita , almacenando las claves en una matriz y utilizando sus posiciones relativas dentro de esa matriz para representar las relaciones padre-hijo.

Operaciones de montón

Tanto la operación de inserción como la de eliminación modifican el montón para preservar su forma original, añadiendo o eliminando elementos del final del mismo. A continuación, se restablece la forma original recorriendo el montón hacia arriba o hacia abajo. Ambas operaciones tienen una complejidad temporal de O(log n ) .

Insertar

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

  1. Agregue el elemento al nivel inferior del montón en el espacio libre más a la izquierda.
  2. Compara el elemento añadido con su elemento padre; si están en el orden correcto, detente.
  3. De lo contrario, intercambie el elemento con su elemento padre y vuelva al paso anterior.

Los pasos 2 y 3, que restauran la propiedad de montón comparando y posiblemente intercambiando un nodo con su padre, se denominan operación de montón ascendente (también conocida como burbuja ascendente , percolar ascendente , filtrar ascendente , goteo ascendente , nadar ascendente , apilar ascendente , cascada ascendente o arreglar ascendente ).

El número de operaciones requeridas depende únicamente del número de niveles que el nuevo elemento debe alcanzar para satisfacer la propiedad de montículo. 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ículo aleatorio y para inserciones repetidas, la operación de inserción tiene una complejidad en el caso promedio de O(1). [ 4 ] [ 5 ]

Una breve animación que muestra cómo se agrega un valor a un montón máximo binario.

La siguiente animación muestra un ejemplo de inserción en un montón binario. Comienza insertando 15 en el montón en la entrada vacía más a la izquierda de la siguiente fila disponible. Sin embargo, la propiedad del montón se viola ya que 15 > 8 , por lo que necesitamos intercambiar el 15 y el 8. Incluso después de este intercambio, la propiedad del montón sigue viéndose violada ya que 15 > 11 , por lo que necesitamos intercambiar de nuevo. La propiedad del montón ahora se satisface, por lo que el árbol binario resultante es un montón máximo válido. No es necesario comprobar el hijo izquierdo después de este último paso: 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 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) manteniendo la propiedad de montón es el siguiente:

  1. Reemplaza la raíz del montón con el último elemento del último nivel.
  2. Compara 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 vuelva al paso anterior. (Intercambie con su hijo menor en un montículo mínimo y con su hijo mayor en un montículo máximo).

Los pasos 2 y 3, que restauran la propiedad de montón comparando y posiblemente intercambiando un nodo con uno de sus hijos, se denominan operación de descenso de montón (también conocida como burbuja descendente , percolar descendente , sift descendente , sink descendente , goteo descendente , heapificar descendente , cascada descendente , corregir descendente , extraer mínimo o extraer máximo , o simplemente heapificar ).

Una breve animación que muestra cómo extraer un valor de un montón máximo binario.

Entonces, si tenemos el mismo montículo máximo que antes, eliminamos el 11 y lo reemplazamos por el 4. Ahora se viola la propiedad del montículo, 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ículo 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ículo máximo (en un montículo mínimo se intercambiaría con su hijo menor), hasta que satisfaga la propiedad del montículo en su nueva posición. Esta funcionalidad se logra mediante la función Max-Heapify , definida a continuación en pseudocódigo para un montículo respaldado por un arreglo A de longitud length ( A ). A se indexa comenzando en 1.

// Realizar una operación de reducción de montón o de reducción de montón para un montón máximo. // A : un array que representa el montón, indexado a partir del 1. // i : el índice en el que comenzar al monticular hacia abajo Max-Heapify ( A , i ): izquierda ← 2× i derecha ← 2× i + 1 mayor ← iSi izquierda ≤ longitud ( A ) y A [ izquierda ] > A[ mayor ] entonces : mayor ← izquierda Si derecha ≤ longitud ( A ) y A [ derecha ] > A [ mayor ] entonces : mayor ← derechaSi largest ≠ i entonces : intercambiar A [ i ] y A [ largest ] Max-Heapify ( A , largest )

Para que el algoritmo anterior reorganice correctamente el array, ningún nodo, aparte del nodo en el índice i y sus dos hijos directos, puede infringir la propiedad de montón. La operación de descenso de montón (sin el intercambio previo) también puede utilizarse para modificar el valor de la raíz, incluso cuando no se elimina ningún elemento.

En el peor de los casos, la nueva raíz tiene que intercambiarse con su hijo en cada nivel hasta que llegue al 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, 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 upheapAND downheap. En cambio, podemos hacer solo una downheapoperación, como se muestra a continuación:

  1. Compara 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. Reemplaza la raíz con el nuevo elemento.
    2. Descomponer en montículos desde la raíz
  3. De lo contrario, devuelva el artículo que estamos enviando.

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

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

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 agrega un nuevo elemento. // montón : un array que representa el montón, indexado en 1. // item : un elemento para insertar // Devuelve la raíz actual del montón Replace ( heap : List<T>, item : T) -> T: intercambia el montón [1] y el elemento _downheap( montón comenzando desde el índice 1) return item

Encontrar un elemento arbitrario requiere un tiempo de O(n).

Esto se puede demostrar fácilmente considerando que el montón no está ordenado, por lo que necesitamos recorrer todo el árbol para encontrar el elemento buscado.

Borrar

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

  1. Encuentra el índicei{\displaystyle i}del elemento que queremos eliminar
  2. Intercambia este elemento con el último. Elimina el último elemento después del intercambio.
  3. Reduzca o aumente la propiedad de montón para restaurarla. En un montón máximo (montón mínimo), solo se requiere aumentar la propiedad de montón cuando la nueva clave del elementoi{\displaystyle i}es mayor (menor) que el anterior porque solo podría violarse la propiedad de montón del elemento padre. Suponiendo que la propiedad de montón fue válida entre elementosi{\displaystyle i}y sus hijos antes del intercambio de elementos, no puede ser violado por un valor de clave ahora mayor (menor). Cuando la nueva clave es menor (mayor) que la anterior, entonces solo se requiere una reducción del montón porque la propiedad del montón solo podría violarse en los elementos hijos.

Disminuir o aumentar la tecla

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 dicho valor y luego reorganizarlo (hacia abajo o hacia arriba) para restaurar la propiedad de montón.

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

  1. Encuentra el índice del elemento que queremos modificar.
  2. Disminuir el valor del nodo
  3. Reduzca el tamaño del montón (suponiendo 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. Aumentar el tamaño del montón (suponiendo un montón máximo) para restaurar la propiedad del montón.

Construyendo un montón

La construcción de un montón a partir de un arreglo de n elementos de entrada se puede realizar 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 ejecuta fácilmente en tiempo O ( n log n ) : realiza n inserciones con un costo O (log n ) cada una. [ a ]

Sin embargo, el método de Williams es subó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, véase más abajo). Luego, comenzando desde el nivel más bajo y moviéndose hacia arriba, se desplaza 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 comienzan en alguna alturah{\displaystyle h}ya han sido "amontonados" (el nivel más bajo correspondiente ah=0{\displaystyle h=0}), los árboles a mayor alturah+1{\displaystyle h+1}se pueden convertir en montículos enviando su raíz hacia abajo a lo largo del camino de los hijos de valor máximo cuando se construye un montículo máximo, o de los hijos de valor mínimo cuando se construye un montículo mínimo. Este proceso llevaO(h){\displaystyle O(h)}operaciones (intercambios) por nodo. En este método, la mayor parte de la acumulación de memoria se produce en los niveles inferiores. Dado que la altura del montón es⌊registro⁡norte⌋{\displaystyle \lfloor \log n\rfloor }, el número de nodos a alturah{\displaystyle h}es≤2⌊registro⁡norte⌋2h≤norte2h{\displaystyle \leq {\frac {2^{\lfloor \log n\rfloor }}{2^{h}}}\leq {\frac {n}{2^{h}}}}Por lo tanto, el costo de convertir todos los subárboles en montones es:

∑h=0⌊registro⁡norte⌋norte2hO(h)=O(norte∑h=0⌊registro⁡norte⌋h2h)=O(norte∑h=0∞h2h)=O(norte){\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∑i=0∞i/2i{\textstyle \sum _{i=0}^{\infty }i/2^{i}}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:

2norte−2s2(norte)−mi2(norte){\displaystyle 2n-2s_{2}(n)-e_{2}(n)}, [ 9 ] [ b ]

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 aproxima asintóticamente a 1,8814 n − 2 log 2 n + O (1)  comparaciones. [ 10 ] [ 11 ]

La función Build-Max-Heap que se describe a continuación convierte un array A que almacena un árbol binario completo con n nodos en un max-heap mediante el uso repetido de Max-Heapify (down-heapify para un max-heap) de forma ascendente. Los elementos del array 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 heap de un solo elemento y no necesita ser down-heapificado. Build-Max-Heap ejecuta Max-Heapify en cada uno de los nodos restantes del árbol.

Construir-Máximo-Montículo ( A ): para cada índice i desde floor ( longitud ( A )/2) hasta 1 hacer: Maximizar-Montículo ( A , i )

Implementación de montón

Un pequeño árbol binario completo almacenado en una matriz
Comparación entre una implementación en montículo binario y una implementación en arreglo.

Los montículos se implementan comúnmente con un array . Cualquier árbol binario puede almacenarse en un array, pero dado que un montículo binario siempre es un árbol binario completo, se puede almacenar de forma compacta. No se requiere espacio para punteros ; en su lugar, el padre y los hijos de cada nodo se pueden encontrar mediante operaciones aritméticas sobre los índices del array. Estas propiedades hacen de esta implementación de montículo un ejemplo sencillo 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 restricciones del 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 las operaciones aritméticas.

Sea n el número de elementos en el montón e i un índice válido arbitrario del arreglo 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 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 los índices 2 i y 2 i +1
  • su padre en el piso del índice ( i /2).

Esta implementación se utiliza en el algoritmo de ordenación por montículos , que reutiliza el espacio asignado al array de entrada para almacenar el montículo (es decir, el algoritmo se ejecuta in situ ). Esta implementación también resulta útil como cola de prioridad . Al utilizar un array dinámico , es posible insertar un número ilimitado de elementos.

Las operaciones upheapOR downheapse pueden expresar en términos de un arreglo de la siguiente manera: supongamos que la propiedad de montón se cumple para los índices b , b +1, ..., e . La función de sift-down extiende la propiedad de montón a b -1, b , b +1, ..., e . Solo el índice i = b -1 puede violar la propiedad de 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 2i > e , entonces la propiedad de montón se cumple 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 de montón para la posición i . En este punto, el único problema es que la propiedad de montón podría no cumplirse para el índice j . La función de sift-down se aplica recursivamente al índice j hasta que se establece la propiedad de montón para todos los elementos.

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

Para grandes montículos y el uso de memoria virtual , almacenar elementos en un arreglo según el esquema anterior es ineficiente: (casi) cada nivel está en una página diferente . Los montículos B son montículos binarios que mantienen los 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 montículos binarios toma Θ( n ) para montículos de igual tamaño. Lo mejor que se puede hacer es (en el caso de una implementación de arreglo) simplemente concatenar los dos arreglos de montículos y construir un montículo con el resultado. [ 13 ] Un montículo de n elementos se puede fusionar con un montículo de k elementos usando O(log n log k ) comparaciones de claves, o, en el caso de una implementación basada en punteros, en tiempo O(log n log k ). [ 14 ] En [ 15 ] se presentó un algoritmo para dividir un montículo de n elementos en dos montículos de k y nk elementos, respectivamente, basado en una nueva visión de los montículos como colecciones ordenadas de submontículos. El algoritmo requiere O(log n * log n ) comparaciones. La visión también presenta un algoritmo nuevo y conceptualmente simple para fusionar montículos. 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 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 "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.O{\displaystyle O}(registro⁡norte){\displaystyle (\log n)}tiempo. [ 16 ] Para ello, las filas alternan entre montículo mínimo y montículo máximo. Los algoritmos son prácticamente iguales, pero, en cada paso, se deben considerar las filas alternas con comparaciones alternas. El rendimiento es prácticamente el mismo que el de un montículo normal de una sola dirección. Esta idea se puede generalizar a un montículo min-max-mediano.

Derivación de ecuaciones de índices

En un montículo basado en arreglos, los hijos y el padre de un nodo se pueden localizar mediante operaciones aritméticas sencillas sobre el índice del nodo. Esta sección deduce las ecuaciones relevantes para montículos con raíz en el índice 0, con notas adicionales sobre montículos con raíz en el índice 1.

Para evitar confusiones, definimos el nivel de un nodo como su distancia a la raíz, de modo que la raíz misma ocupa el nivel 0.

nodos hijos

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

Sea el nodo i ubicado en el nivel L , y observemos que cualquier nivel l contiene exactamente2l{\displaystyle 2^{l}}nodos. Además, hay exactamente2l+1−1{\displaystyle 2^{l+1}-1}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(k−1){\displaystyle (k-1)}. Al combinar estas observaciones, se obtiene la siguiente expresión para el índice del último nodo en la capa l .

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

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

i=último(L)−j=(2L+1−2)−j{\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 haber2j{\displaystyle 2j}nodos que separan el hijo derecho de i del final de su capa (L+1{\displaystyle L+1}).

bien=último(L + 1)−2j=(2L+2−2)−2j=2(2L+1−2−j)+2=2i+2{\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 siempre está 1 lugar antes que su hijo derecho, obtenemosizquierda=2i+1{\displaystyle {\text{left}}=2i+1}.

Si la raíz se encuentra en el índice 1 en lugar de 0, el último nodo en cada nivel se encuentra en el índice2l+1−1{\displaystyle 2^{l+1}-1}. Usando esto en todo momento se obtienenizquierda=2i{\displaystyle {\text{left}}=2i}ybien=2i+1{\displaystyle {\text{right}}=2i+1}para montones con su raíz en 1.

Nodo padre

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

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

Por eso,

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

Ahora consideremos la expresión⌊i−12⌋{\displaystyle \left\lfloor {\dfrac {i-1}{2}}\right\rfloor }.

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

⌊i−12⌋=⌊i−22+12⌋=i−22=padre{\displaystyle {\begin{alignedat}{2}\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 un hijo izquierdo o derecho, su padre se puede encontrar mediante la expresión:

padre=⌊i−12⌋{\displaystyle {\text{parent}}=\left\lfloor {\dfrac {i-1}{2}}\right\rfloor }

Dado que el orden de los nodos hermanos en un montón no está especificado por la propiedad de montón, los dos hijos de un mismo nodo pueden intercambiarse libremente, a menos que esto viole la propiedad de forma (compárese con treap ). Sin embargo, tenga en cuenta que en el montón común basado en arreglos, simplemente intercambiar los hijos también podría requerir mover los nodos del subárbol de los hijos para mantener la propiedad de montón.

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

Resumen de los tiempos de carrera

Aquí se muestran las complejidades temporales [ 17 ] 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.

  1. ↑ De hecho, se puede demostrar que este procedimiento requiereun tiempo Θ( n log n ) en el peor de los casos , lo que significa que n log n también es una cota inferior asintótica de la complejidad. [ 1 ] : 167 Sin embargo, en el caso promedio (promediando sobre todas las permutaciones de n entradas), el método requiere un tiempo lineal. [ 8 ]
  2. ↑ Esto no significa que la ordenación se pueda realizar en tiempo lineal, ya que la construcción de un montón es solo el primer paso del algoritmo de ordenación por montículos .
  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 entiempo Θ ( n ) siempre que meld se ejecute en tiempo O (log n ) (donde ambas complejidades se pueden amortizar). [ 18 ] [ 19 ] Otro algoritmo alcanza Θ ( n ) para montones binarios. [ 20 ] 
  4. 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 . [ 23 ] 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. [ 22 ] 
  5. ↑ Límite inferior deΩ(registro⁡registro⁡norte),{\displaystyle \Omega (\log \log n),}[ 26 ] límite superior deO(22registro⁡registro⁡norte).{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}[ 27 ]
  6. 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 .

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", Communications of the ACM , 7 (6): 347– 348, doi : 10.1145/512274.3734138
  3. ↑ Y Narahari, "Montículos 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 . Bibcode : 1975ITSEn...1..292P . doi : 10.1109/TSE.1975.6312854 . ISSN 1939-3520 . S2CID 18907513 .  
  5. ↑ Mehlhorn, Kurt; Tsakalidis, A. (feb. 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 demostración no se generaliza 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á acotado por 1,7645. El costo del peor caso de 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 forma más eficiente que heappush() seguido de una llamada separada a heappop().
  8. 1 2 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 . 
  9. ↑ Suchenek, Marek A. (2012), "Análisis elemental pero preciso del peor caso del programa de construcción de montones de Floyd" , Fundamenta Informaticae , 120 (1): 75–92 , doi : 10.3233/FI-2012-751.
  10. ↑ Doberkat, Ernst E. (mayo de 1984). "Análisis del caso promedio del algoritmo de Floyd para construir montículos" (PDF) . Information and Control . 6 (2): 114– 131. doi : 10.1016/S0019-9958(84)80053-4 .
  11. ↑ Pasanen, Tomi (noviembre de 1996). Análisis elemental del caso promedio del algoritmo de Floyd para la construcción de montículos (Informe técnico). Centro de Ciencias de la Computación de Turku. CiteSeerX 10.1.1.15.9526 . ISBN  951-650-888-XInforme técnico TUCS nº 64. Tenga 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.º 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. ↑ Sack, Jörg-Rüdiger ; Strothotte, Thomas (1990). "Una caracterización de los montículos y sus aplicaciones" . Information and Computation . 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). "Montículos min-max y colas de prioridad generalizadas" (PDF) . Técnicas de programación y estructuras de datos. Comm. ACM, 29(10): 996–1000. Archivado del original (PDF) el 27 de enero de 2007. Recuperado el 29 de abril de 2008 .
  17. 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.
  18. 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 .  
  19. 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.
  20. ↑ 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 . 
  21. ↑ "Montículo binomial | Brilliant Math & Science Wiki" . brilliant.org . Consultado el 30 de septiembre de 2019 .
  22. 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
  23. ↑ Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). págs. 158–162 . ISBN   9780521631242.
  24. ↑ Takaoka, Tadao (1999), Teoría de los montículos 2-3 (PDF) , pág. 12 
  25. ↑ 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
  26. ↑ 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 .
  27. ↑ 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.
  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). "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 . 
  30. ↑ 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.
  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.
  • Estructuras de datos abiertas - Sección 10.1 - BinaryHeap: Un árbol binario implícito , Pat Morin
  • Implementación de un montón máximo binario en C por Robin Thomas
  • Implementación de un montón mínimo binario en C por Robin Thomas