Download Cap. 21. Colas de prioridad. Pairing heaps.

1
Capítulo 21
Heaps Binomiales. Seleccionar.
Una cola de prioridad binomial considera los datos almacenados en una foresta; ésta puede ser
definida como una colección de subárboles, en la que cada subárbol es un árbol binomial; y tal
que cada uno de ellos cumple la propiedad de que los hijos tienen claves o prioridades mayores
o iguales a las del padre. Esta estructura favorece la operación de mezclar dos colas de
prioridad, para formar una nueva.
21.1. Árbol binomial.
Un árbol binomial B p 1 , de orden p+1, es un multiárbol formado por la unión de dos árboles
0 . B0 está formado por un elemento. Entendemos por unión el
que la raíz de uno de los árboles binomiales B p es el hijo más izquierdista de la raíz del otro
binomiales de orden p, para p
árbol binomial B p , según se muestra en la Figura 21.1.
B0
Bp+1
Bp
Bp
Figura 21.1. Definición inductiva de árbol binomial.
La Figura 21.2, muestra algunos ejemplos de árboles binomiales.
B0
B1
B2
B3
Figura 21.2. Ejemplos de árboles binomiales.
Puede demostrarse por inducción que un árbol binomial B p tiene 2 p nodos; que la raíz tiene p
hijos; y que la máxima profundidad del árbol es p.
Profesor Leopoldo Silva Bijit
20-01-2010
2
Estructuras de Datos y Algoritmos
Es importante destacar que si n 2 p , entonces: p log 2 (n) . Las principales operaciones sobre
esta estructura dependen del número de hijos de la raíz.
Si se enumeran los nodos, empleando el sistema binario, en preorden (izquierdo-derecho-raíz),
partiendo del nodo con mayor profundidad, se obtiene la Figura 21.3, para el caso de B3 .
111
011
001
010
101
110
100
000
Figura 21.3. Numeración binaria en preorden de B3.
Se tienen
p
k
nodos con profundidad k en B p . Debido al coeficiente binomial, que figura en la
relación anterior, se da el nombre de binomiales a estos árboles.
Para la raíz y el nodo más profundo de B p , se tienen:
Los p hijos de la raíz de B p , se obtienen de:
p
1
p
p
p
0
p!
1!( p 1)!
1.
p.
Los valores de los coeficientes binomiales corresponden al número de secuencias binarias de p
bits, con exactamente k ceros. También puede comprobarse que las hojas tienen números pares;
y que el número de hijos de un nodo es el número de unos que siguen al último cero de su
numeración binaria.
Como Bp está formado por la unión de dos árboles Bp-1, un nodo a profundidad k en Bp-1 aparece
en Bp una vez a profundidad k y una vez a profundidad k + 1. Entonces para obtener los nodos a
profundidad k en Bp debemos sumar los nodos a profundidad k en Bp-1, más los nodos a
profundidad k-1 en Bp-1.
k-1
k
Figura 21.4. Nodo con profundidad k en Bp.
Considerando verdadera la proposición inductiva, debería cumplirse:
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
3
p
p 1
p 1
k
k
k 1
Desarrollando el lado derecho, y aplicando la definición de coeficiente binomial, se obtiene:
( p 1)!
( p 1)!
k !( p 1 k )! (k 1)!( p 1 (k 1))!
Sacando factores comunes, y multiplicando y dividiendo el segundo término por k, se tiene:
( p 1)!
1
k
(
)
k!
( p 1 k )! ( p k )!
Multiplicando y dividiendo el primer término por p-k, factorizando y aplicando la definición de
coeficiente binomial, se tiene:
( p 1)!
(( p k ) k )
k !( p k )!
p!
k !( p k )!
p
k
Lo que demuestra la propiedad.
Una forma alternativa de definir B p 1 , es agregar como hijos de la raíz a los (p+1) árboles
binomiales: B p , B p 1 , B p 2 ,..., B2 , B1 , B0 . La Figura 21.5, muestra la generación de B3 .
B3
B2
B1
B0
Figura 21.5. Subárboles de B3.
21.2. Cola de prioridad binomial.
Si se desea representar conjuntos de n elementos, tal que n no sea una potencia de dos, puede
considerarse la representación de n en el sistema binario, mediante la secuencia de (p+1) cifras
binarias, con el equivalente decimal:
i p
bi 2i
n
i 0
Profesor Leopoldo Silva Bijit
20-01-2010
4
Estructuras de Datos y Algoritmos
Donde bi es uno de los dígitos binarios {0, 1}. Se define la foresta binomial Fn de orden n,
como una colección finita de árboles binomiales Bi , uno por cada cifra bi diferente de cero en la
representación binaria de n.
Por ejemplo para n=13, se tiene: F13
B3 , B2 , B0 ya que 1310
11012
Entonces una cola de prioridad de n elementos puede ser representada por una foresta Fn , donde
cada uno de los árboles binomiales que la forman, cumplen la propiedad de que los hijos tienen
prioridades mayores que la de su padre.
Observando la Figura 21.5, una cola de prioridad con n elementos también puede representarse
con la raíz como el nodo con prioridad mínima unido a una foresta Fn-1.
21.3. Análisis de la operación unión.
Dadas dos forestas: Fn y Fm la unión estará formada por (n+m) elementos en una foresta Fn m .
Es notable que la operación mezcla pueda realizarse en forma similar a una suma binaria. El
siguiente ejemplo describe el algoritmo:
Se desea obtener la mezcla de F13
B3 , B2 , B0 con F5
B2 , B0 . La suma binaria de 13 y
5, se realiza según:
1 1 0 1
+ 0 1 0 1
1 0 0 1 0
Al sumar (unir, mezclar o fundir) dos árboles binomiales Bi se produce reserva, ésta es un árbol
binomial Bi 1 .
+
B4
B3 B2
B2
Entonces, para el ejemplo, resulta: F18
B0
B0
B1
B4 , B1 .
Observando la Figura 21.2, puede notarse que la unión de dos árboles binomiales puede
realizarse en tiempo constante, basta escribir una referencia para el árbol descendiente. En el
peor caso un heap con n elementos está formado por log(n) árboles binomiales, entonces
obtener uno, mediante mezclas, demanda un costo O(log(n)).
La inserción puede realizarse como la mezcla de un árbol binomial con un elemento con la
estructura ya existente. También su costo es O(log(n)).
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
5
La extracción del mínimo requiere buscar la raíz menor de los árboles binomiales que forman la
foresta, esto tiene un costo O(log(n)), ya que ese es el número de heaps que forman la cola de
prioridad. Observando la Figura 21.5, la remoción de la raíz de uno de los árboles binomiales
genera una nueva foresta, la cual debe unirse al resto de los árboles binomiales, lo cual se
realiza también en O(log(n-1)), dando para la operación completa un costo O(log(n)).
21.4. Estructura de datos.
La Figura 21.6, muestra las prioridades almacenadas en los multiárboles binomiales: B3 , B2, B1 ,
B0.
1
1
2
2
1
1
3
4
2
5
3
6
7
4
8
Figura 21.6. Multiárboles binomiales: B3 , B2, B1 , B0.
21.4.1. Nodo binario.
Inicialmente se considera un nodo binario, que minimiza el tamaño de memoria ocupada por el
nodo.
La Figura 21.7, muestra una posible estructura que emplea los punteros derechos para
referenciar el hijo más derechista del nodo, y los punteros izquierdos para enlazar los hermanos
hacia la izquierda. Las listas de hermanos son circulares: Si no hay hermanos de un nodo, el
puntero izquierdo apunta al mismo nodo; el último nodo de la lista de hermanos apunta al
hermano más derechista. Las hojas tienen punteros derechos, o hacia abajo, nulos.
Se han ilustrado árboles binomiales, donde la raíz tiene lista izquierda vacía, sin embargo puede
acordarse unir los árboles binomiales de la foresta en la lista circular de la raíz.
Profesor Leopoldo Silva Bijit
20-01-2010
6
Estructuras de Datos y Algoritmos
1
1
1
2
2
1
3
2
5
3
4
6
7
4
8
Figura 21.7. Representación mediante listas.
Por ejemplo si a B1 en la Figura 21.7, se agrega un nodo con prioridad 3, el árbol binomial B0,
que lo representa, se coloca en la lista izquierda de la raíz, esto se muestra en la Figura 21.8.
Debe notarse que la operación es sencilla si el número de elementos en la foresta es par; ya que
esto implica agregar el árbol binomial B0, formado por un elemento.
3
1
2
Figura 21.8. Foresta con 3 elementos.
Si en B2 en la Figura 21.7, se agregan nodos con prioridades 5 y 6, debe formarse el árbol
binomial B1 , el cual se coloca en la lista izquierda de la raíz, formando una foresta de 6
elementos, esto se muestra en la Figura 21.9, a la izquierda. Nótese que después de agregado el
5, debe procederse a formar, mediante la unión o suma un árbol binomial B1, formado por los
elementos 5 y 6.
A la derecha de la Figura 21.8, se muestra un foresta con 7 elementos, donde se ha enlazado B0,
formado por el nodo con valor 7, con B1 y B2. Esta inserción también es sencilla.
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
5
2
6
7
1
5
3
6
7
1
2
3
4
4
Figura 21.9. Foresta con 6 y 7 elementos.
La inserción del elemento con valor 8, en el heap a la derecha de la Figura 21.9, debería formar
el árbol binomial B3, que se muestra a la derecha de la Figura 21.7. Esto se logra con la unión de
dos árboles B1, para formar un árbol B2; y luego la suma de dos árboles B2, para formar un árbol
B3.
+
B3
B2 B1 B0
B0
Figura 21.10. Generación de B3 mediante mezclas.
21.4.2. Nodo binario aumentado con información del grado.
Si se almacena el número de elementos en la foresta, su representación binaria indica los árboles
binomiales que la forman. Si al inicio, antes de insertar, el número de elementos es impar, esto
indica que está presente B0; y si es par, indica que la foresta no contiene a B0. La división
sucesiva de este número por dos va indicando, en la cifra binaria menos significativa, si están
presentes en la cola de prioridad los árboles binomiales B1, B2, y así sucesivamente. Sin
embargo, con esta estructura, la operación para extraer el mínimo es compleja de codificar.
Si se almacena el grado del árbol binomial en el nodo, puede representarse la foresta como una
lista enlazada de las raíces de los árboles binomiales ordenadas por grado, ya que esto facilita la
operación unión de dos árboles binomiales de igual grado. Sin embargo el descarte del mínimo
requiere recorrer la lista completa, pero el largo de ésta está acotada; el largo, en el peor caso, es
el logaritmo del número de nodos almacenados en la cola de prioridad. Para representar los
multiárboles se emplea la organización hijo más izquierdista-hermano derecho.
La Figura 21.11, muestra los multiárboles binomiales B2 y B3 de la Figura 21.6, empleando el
enlace izquierdo del nodo binario para apuntar al hijo más izquierdista, y el enlace derecho para
apuntar al hermano derecho; en cada nodo se almacena la prioridad y el grado del árbol
binomial asociado al nodo. Nótese que dentro del árbol binomial, las listas de hermanos están
ordenadas en forma descendente según el grado, esto facilita la operación unión de dos árboles
binomiales de igual grado, basta escribir dos punteros e incrementar el grado de la nueva raíz.
Esto se ilustra a la derecha de la Figura 21.11, destacando los dos árboles que se unen.
Profesor Leopoldo Silva Bijit
20-01-2010
8
Estructuras de Datos y Algoritmos
1
3
3
1
5
2
1
2
3
1
7
1
2
0
6
0
2
0
4
0
8
0
4
0
Figura 21.11. Representación hijo izquierdo-hermano derecho de B2 y B3.
La Figura 21.12, muestra una cola de prioridad con 13 nodos, mediante el enlace de tres árboles
binomiales: B0, B2 y B3. El enlace derecho de las raíces de los árboles binomiales se emplea
para formar una lista ordenada en forma descendente por grado; debe notarse que no quedan
ordenados por prioridad. El ejemplo muestra que el nodo con prioridad mínima puede estar en
cualquier posición de la lista; en la Figura 21.12, se ilustra al final de ésta.
9
0
1
3
10
2
11
1
12
0
3
1
5
2
7
1
14
0
6
0
2
0
4
0
8
0
Figura 21.12. Foresta con 13 nodos. Lista de raíces.
Ordenando de este modo la lista, se facilita la operación de unir (o sumar) dos forestas. Equivale
a realizar las sumas binarias desde los dígitos menos significativos.
21.4.3. Nodo binario con punteros al padre.
Si se desea disponer de operaciones de búsqueda o de decrementar la prioridad de un nodo, para
que estas operaciones resulten eficientes, debe agregarse un puntero al padre.
21.5. Análisis de la inserción.
Si la foresta no contiene un árbol binomial B0, la inserción coloca el nuevo nodo al comienzo de
la lista de raíces. Si está presente B0, se une a éste el nodo que se desea insertar, formando un
árbol binomial B1; y debe seguirse efectuado uniones si pueden formarse árboles binomiales de
mayores grados, esto se realiza recorriendo la lista de raíces.
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
9
Si antes de la inserción, la foresta no puede tener dos árboles binomiales de igual grado,
entonces la lista debe recorrerse mientras el grado de la última unión sea igual al grado del
siguiente árbol binomial de la lista.
21.6. Análisis de la extracción del mínimo.
Se recorre la lista hasta encontrar el mínimo, y se liga la lista con el siguiente. Los hijos del
nodo mínimo forman otra lista de árboles binomiales; sin embargo, debido a la construcción,
está ordenada por grados en forma descendente. Entonces se debe reversar la lista de hijos del
nodo mínimo, dejándola ordenada en forma ascendente por grado.
Luego se procede a mezclar las dos listas ordenadas por grados, dejando adyacentes a los nodos
que tengan grados iguales. Luego debe procederse a unir los árboles de igual grado, y si es
posible, formar árboles de mayores grados; esta operación debe recorrer la lista completa.
21.7. Tipos de datos.
Se considera un nodo binario más la información del grado. De ser necesario puede emplearse
un puntero al padre.
typedef struct bintree
{ //struct bintree * padre;
struct bintree * hijo;
struct bintree * hermano;
int prioridad;
int grado;
} nodo, *pnodo;
//puntero al hijo más izquierdista.
//apunta al hermano derecho
typedef pnodo queue;
21.8. Creación de nodo.
pnodo getnodo(int prioridad)
{ pnodo p=NULL;
if ( (p= (pnodo) malloc(sizeof(nodo))) ==NULL)
{ printf("Error: Memoria. \n"); exit(1);}
else
{ p->prioridad=prioridad; p->grado=0;
//p->padre=NULL;
p->hijo=NULL; p->hermano=NULL;
}
return(p);
}
21.9. Inicio de cola.
void initqueue( queue *q )
Profesor Leopoldo Silva Bijit
20-01-2010
10
Estructuras de Datos y Algoritmos
/* inicia una variable de tipo cola de prioridad */
{
*q = NULL;
} /* initqueue */
21.10. Test de cola vacía.
int emptyqueue( queue q )
/* Retorna 1 si la cola está vacía */
{
return (q == NULL);
} /* emptyqueue */
21.11. Unión de dos árboles binomiales de igual grado.
Enlaza árbol de grado (k-1) con raíz mayorp, con árbol de grado (k-1) con raíz menorp, por
nodo con menor prioridad. Ver Figura 1.
Donde menorp es el padre de mayorp, y además es la raíz de un nuevo árbol de grado k. Se
coloca como comentario, la mantención de punteros al padre.
void BinomialLink(pnodo mayorp, pnodo menorp)
{ //mayorp->padre=menorp;
mayorp->hermano=menorp->hijo;
menorp->hijo= mayorp;
menorp->grado++;
}
menorp
1
3
mayorp
3
1
5
2
7
1
6
0
2
0
4
0
8
0
Figura 21.13. Enlace de dos árboles de grado 2.
21.12. Mezcla dos listas ordenadas por campo grado.
pnodo BinomialHeapMerge(pnodo H1, pnodo H2)
{ pnodo H=NULL, t;
if (H1==NULL ) return H2; else if (H2==NULL) return H1;
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
11
else
{ if (H1->grado < H2->grado) {H=H1; H1=H1->hermano;} //Inicio lista
else {H=H2; H2=H2->hermano;}
t=H;
while(H1!=NULL && H2!=NULL) //se pasan en orden ascendente
{ if (H1->grado < H2->grado){t->hermano=H1; H1=H1->hermano;}
else {t->hermano=H2; H2=H2->hermano;}
t=t->hermano;
}
if (H1!=NULL ) t->hermano=H1; //copia el resto de la lista que no se agotó
else t->hermano=H2;
return(H);
}
}
Puede compactarse la codificación de la función si se emplea un nodo de encabezado, de este
modo la inicialización de la mezcla se realiza dentro del lazo while.
pnodo BinomialHeapMerge(pnodo H1, pnodo H2)
{ nodo h;
pnodo t=&h;
while (H1!=NULL && H2!=NULL)
{ if (H1->grado < H2->grado){t->hermano=H1; H1=H1->hermano;}
else {t->hermano=H2; H2=H2->hermano;}
t=t->hermano;
}
if (H1==NULL ) t->hermano=H2;
else if (H2==NULL ) t->hermano=H1; else t->hermano=NULL;
return ((&h)->hermano);
//retorna puntero a la mezcla.
}
21.13. Mezcla dos colas binomiales.
Es la operación fundamental de la estructura. Su costo depende del largo de la lista de árboles
binomiales.
Si dos árboles adyacentes son de grados diferentes, debe seguir revisando la lista. También debe
seguir revisando sin efectuar enlaces, si se encuentran tres árboles binomiales de igual grado; si
esto ocurre, avanza una posición, dejando uno de los árboles y mezclando los dos siguientes.
Este caso equivale a la suma de dos dígitos binarios con reserva.
La función emplea tres punteros para el análisis de los casos: un puntero al nodo previo, otro al
actual, y otro al siguiente. Al inicio el puntero previo apunta a nulo.
Debido a que los operadores lógicos operan con cortocircuitos, la realización de la segunda
parte de un or, sólo se efectúa si el primer operando es falso; ya que si el primero es verdadero
la condición será verdadera no importando el valor lógico de la segunda. Entonces, la detección
de tres adyacentes iguales puede codificarse, como el segundo término del or, según:
Profesor Leopoldo Silva Bijit
20-01-2010
12
Estructuras de Datos y Algoritmos
(x->grado != nextx->grado ||
( (nextx->hermano!= NULL) && (nextx->hermano->grado == x->grado)) )
La formulación de la segunda parte del or, se plantea mediante un and lógico para asegurar la
existencia del tercer nodo; ya que si no existe el tercer nodo, preguntar por su grado produce un
error en ejecución.
El caso 1, se produce cuando los nodos raíces tienen grados diferentes, y se activa con la
primera parte del or. El caso 2, se presenta cuando existe suma de árboles binomiales de igual
grado con reserva.
Cuando debe efectuarse el enlace binomial de dos árboles de igual grado, se tienen dos casos
que se disciernen según la prioridad de los nodos raíces. Son los casos 3 y 4. Se emplea el
puntero previo para enlazar las listas.
pnodo BinomialHeapUnion(pnodo H1, pnodo H2)
{ pnodo H=NULL, prevx, nextx, x;
H = BinomialHeapMerge(H1, H2);
if (H ==NULL) return H;
prevx = NULL;
x = H;
nextx = x->hermano;
while (nextx != NULL)
{ //Si grado de x y siguiente son diferentes o tres de grados iguales
if (x->grado != nextx->grado ||
((nextx->hermano!= NULL) && (nextx->hermano->grado == x->grado)) )
{ prevx = x;
// Casos 1 y 2. Avanza sin enlazar árboles.
x = nextx;
}
//Entra al else: Si grados de x y siguiente son iguales
//y no hay tres nodos de iguales grados adyacentes.
else if (x->prioridad <= nextx->prioridad ) // Caso 3
{ x->hermano = nextx->hermano;
//Liga lista y deja
BinomialLink(nextx, x);
//x como raíz
}
else
{if (prevx == NULL) H = nextx; // Caso 4
else prevx->hermano= nextx;
//Liga lista y deja a
BinomialLink(x, nextx);
//nextx en la raíz
x = nextx;
//actualiza el nodo denominado actual
}
nextx = x->hermano; //avanza al siguiente
}
return H;
}
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
13
21.14. Insertar.
Se pasa la cola de prioridad con una referencia a ésta.
Encola nodo n en cola referenciada por q, empleando la operación de unión.
void enqueue( pnodo n, queue *q )
{ pnodo p=*q;
*q= BinomialHeapUnion(p, n);
} /* enqueue */
Una pequeña refinación de la operación, se logra aislando dos situaciones triviales. La primera
es que la cola esté vacía; la otra es que el número de nodos en la foresta sea par, en este caso no
hay al principio de la lista un árbol binomial de un nodo, o de grado cero, y basta insertar al
inicio. Puede especializarse aún más la operación, ya que en este caso no pueden presentarse
tres árboles de igual grado, y tampoco es preciso recorrer toda la lista.
void enqueue( pnodo n, queue *q )
{ pnodo p=*q;
if (p==NULL) *q=n;
else if (p->grado!=0) {n->hermano=*q; *q=n;}
else
*q= BinomialHeapUnion(p, n);
} /* enqueue */
21.15. Descartar.
La operación desencolar retorna el nodo con valor mínimo de prioridad, y deja una foresta
disminuida en un elemento.
Para esto, luego de extraer de la lista el árbol binomial cuya raíz es el nodo con prioridad
mínima, deja ligada la lista con los árboles binomiales siguientes al que contiene el mínimo.
Posteriormente reversa el orden de la lista de hijos del mínimo, dejándola ordenada ascendente.
Finalmente realiza la suma de las dos forestas.
pnodo dequeue( queue *q )
{ pnodo p=*q, min, ListaHijosMinimo;
if (p==NULL) return NULL;
min=ExtraeMinimo(q);
//Se enlaza lista sin el árbol cuya raíz es el mínimo
//reversar lista descendente (ordenada por grado) de hijos del mínimo, apuntada por x.
ListaHijosMinimo=ReversarLista(min->hijo);
//Queda lista ordenada ascendente por grado, apuntada por x.
//Se mezcla lista de árboles sin el mínimo, con la lista de hijos del mínimo
*q=BinomialHeapUnion(*q, ListaHijosMinimo);
return (min);
} /* dequeue */
Profesor Leopoldo Silva Bijit
20-01-2010
14
Estructuras de Datos y Algoritmos
21.16. Extracción del mínimo.
Se emplean variables locales que apuntan al nodo actual de la lista p, y al nodo mínimo min.
Además para facilitar el ligado de la lista se emplean punteros al padre de p (pp) y al padre de
min (pm). Se enlaza lista sin el árbol cuya raíz es el mínimo
pnodo ExtraeMinimo(queue *q)
{ pnodo p=*q, min, pm, pp;
//pp padre de p (hermano izquierdo de p). pm padre del minimo.
pp=NULL; //al inicio p no tiene padre
//min apunta al mínimo. Al inicio apunta al primer nodo de la lista.
min=p; pm=pp;
pp=p; p=p->hermano; //Avanza al siguiente de la lista
while (p!=NULL)
{ if (min->prioridad > p->prioridad) { min=p; pm=pp;}
pp=p; p=p->hermano;
}
if (pm==NULL) *q=min->hermano; //cambia la raíz. Si el mínimo era el primero.
else pm->hermano=min->hermano; //liga resto de la lista
return (min);
}
El código puede simplificarse usando un nodo de encabezado, lo que permite tratar al primer
nodo dentro del lazo while. Se coloca el máximo valor de prioridad en el nodo centinela, de
acuerdo al tipo del campo prioridad; estos valores se encuentran en <limits.h>.
pnodo ExtraeMinimo(queue *q)
{ nodo n ={NULL, NULL, INT_MAX, 0};
//centinela con la prioridad mayor posible
pnodo p=*q, min=&n, pm, pp=NULL;
while (p!=NULL)
{ if (min->prioridad > p->prioridad) { min=p; pm=pp;}
pp=p; p=p->hermano;
}
if (pm==NULL) *q=min->hermano; //cambia la raíz
else pm->hermano=min->hermano; //liga resto de la lista
return(min);
}
21.17. Reversar Lista.
Reversar lista descendente, ordenada por grado, de hijos del mínimo, apuntada por x, dejándola
ordenada en forma ascendente. La operación contempla el caso en que la estructura emplee
punteros al padre, dejando como comentarios las mantenciones de esos punteros.
Se emplean los punteros y y t, para recorrer la lista. Donde y es el siguiente de x, y t el siguiente
de y.
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
pnodo ReversarLista(pnodo x)
{ pnodo y, t;
if (x!=NULL)
{ //x->padre=NULL;
y=x->hermano;
x->hermano=NULL;
while(y!=NULL)
{ //y->padre=NULL;
t=y->hermano;
y->hermano=x;
x=y; y=t;
}
}
return(x);
}
15
//Inicia siguiente del primero de la lista.
//Inicia el primer nodo como el último o fin de lista
//salva dirección del siguiente
//apunta hacia atrás
//recorre la lista
21.18. Busca mínimo.
La siguiente función retorna un puntero al nodo con valor de prioridad mínima, pero no lo
extrae de la foresta.
/*retorna puntero al nodo con prioridad mínima en un heap binomial con n elementos*/
pnodo BinomialHeapMinumun(queue *q)
{
pnodo pmin =NULL; //puntero al mínimo, aún no se conoce
pnodo p =*q;
int min =INT_MAX;
while (p!=NULL)
{ if (p->prioridad < min) { min = p->prioridad; pmin = p;}
p =p->hermano;
}
return pmin;
}
21.19. Lista de raíces de árboles binomiales.
Para ayudar a la depuración de la funciones es conveniente disponer de un listador simple de la
estructura.
//lista raíz-grado
int prtbinomial(queue *q)
{
pnodo p=*q, t;
if (p!=NULL) printf("%d-%d ", p->prioridad, p->grado);
else {printf("Binomial nulo\n"); return(0);}
Profesor Leopoldo Silva Bijit
20-01-2010
16
Estructuras de Datos y Algoritmos
for(t=p->hermano; t!=NULL ; t=t->hermano)
printf("%d-%d ", t->prioridad, t->grado);
putchar('\n');
return(1);
}
21.20. Test de las funciones.
queue binomial=NULL;
#define N 30
int main (void)
{ pnodo t;
int i;
initqueue( &binomial);
srand(1);
for(i=1;i<=N;i++)
{ enqueue2(getnodo(rand()%100), &binomial);
//prtbinomial(&binomial);
}
putchar('\n');
for(i=1;i<=N;i++)
{ t= dequeue(&binomial);
//prtbinomial(&binomial);
printf(" %d ", t->prioridad);
free(t);
}
putchar('\n');
return(0);
}
Referencias.
J. Vuillemin, “A Data Structure for Manipulating Priority Queues”, CACM Vol. 21, No. 4,
April 1978, 309-315.
M. R. Brown. PhD thesis, “The Analysis of a Practical and Nearly Optimal Priority Queue”,
Stanford University, March 1977.
Douglas W. Jones, “An Empirical Comparison of Priority-Queue and Event-Set
Implementations”, Communications of the ACM, April 1986, Volume 29, Number 4.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. “Introduction
to Algorithms”, Second Edition. MIT Press and McGraw-Hill, 2001.
Profesor Leopoldo Silva Bijit
20-01-2010
Colas de prioridad. Heaps Binomiales.
17
Índice general.
CAPÍTULO 21 ........................................................................................................................................... 1
HEAPS BINOMIALES. SELECCIONAR. ............................................................................................. 1
21.1. ÁRBOL BINOMIAL. ........................................................................................................................... 1
21.2. COLA DE PRIORIDAD BINOMIAL. ...................................................................................................... 3
21.3. ANÁLISIS DE LA OPERACIÓN UNIÓN. ................................................................................................ 4
21.4. ESTRUCTURA DE DATOS................................................................................................................... 5
21.4.1. Nodo binario. .......................................................................................................................... 5
21.4.2. Nodo binario aumentado con información del grado. ............................................................ 7
21.4.3. Nodo binario con punteros al padre........................................................................................ 8
21.5. ANÁLISIS DE LA INSERCIÓN. ............................................................................................................ 8
21.6. ANÁLISIS DE LA EXTRACCIÓN DEL MÍNIMO. ..................................................................................... 9
21.7. TIPOS DE DATOS............................................................................................................................... 9
21.8. CREACIÓN DE NODO......................................................................................................................... 9
21.9. INICIO DE COLA................................................................................................................................ 9
21.10. TEST DE COLA VACÍA. .................................................................................................................. 10
21.11. UNIÓN DE DOS ÁRBOLES BINOMIALES DE IGUAL GRADO. ............................................................. 10
21.12. MEZCLA DOS LISTAS ORDENADAS POR CAMPO GRADO. ............................................................... 10
21.13. MEZCLA DOS COLAS BINOMIALES. ............................................................................................... 11
21.14. INSERTAR..................................................................................................................................... 13
21.15. DESCARTAR. ................................................................................................................................ 13
21.16. EXTRACCIÓN DEL MÍNIMO. .......................................................................................................... 14
21.17. REVERSAR LISTA. ........................................................................................................................ 14
21.18. BUSCA MÍNIMO. ........................................................................................................................... 15
21.19. LISTA DE RAÍCES DE ÁRBOLES BINOMIALES. ................................................................................ 15
21.20. TEST DE LAS FUNCIONES. ............................................................................................................. 16
REFERENCIAS. ........................................................................................................................................ 16
ÍNDICE GENERAL. ................................................................................................................................... 17
ÍNDICE DE FIGURAS................................................................................................................................. 17
Índice de figuras.
FIGURA 21.1. DEFINICIÓN INDUCTIVA DE ÁRBOL BINOMIAL. ........................................................................ 1
FIGURA 21.2. EJEMPLOS DE ÁRBOLES BINOMIALES. ...................................................................................... 1
FIGURA 21.3. NUMERACIÓN BINARIA EN PREORDEN DE B3. .......................................................................... 2
FIGURA 21.4. NODO CON PROFUNDIDAD K EN BP. ......................................................................................... 2
FIGURA 21.5. SUBÁRBOLES DE B3. ................................................................................................................ 3
FIGURA 21.6. MULTIÁRBOLES BINOMIALES: B3 , B2, B1 , B0. ......................................................................... 5
FIGURA 21.7. REPRESENTACIÓN MEDIANTE LISTAS. ..................................................................................... 6
FIGURA 21.8. FORESTA CON 3 ELEMENTOS. .................................................................................................. 6
FIGURA 21.9. FORESTA CON 6 Y 7 ELEMENTOS. ............................................................................................ 7
FIGURA 21.10. GENERACIÓN DE B3 MEDIANTE MEZCLAS. ............................................................................. 7
FIGURA 21.11. REPRESENTACIÓN HIJO IZQUIERDO-HERMANO DERECHO DE B2 Y B3. .................................... 8
FIGURA 21.12. FORESTA CON 13 NODOS. LISTA DE RAÍCES........................................................................... 8
Profesor Leopoldo Silva Bijit
20-01-2010
18
Estructuras de Datos y Algoritmos
FIGURA 21.13. ENLACE DE DOS ÁRBOLES DE GRADO 2. ...............................................................................10
Profesor Leopoldo Silva Bijit
20-01-2010