Fibonacci Heap

Fibonacci Heap (Monticulo de Fibonacci) Objetivo: El principal uso que se le puede asociar a esta nueva estructura es buscar el elemento menor de una coleccion de elementos, que por ejemplo, seran usados en una cola de prioridad , en el menor tiempo posible, que es reducido en comparación a estructuras similares como lo es el Binomial Heap. Introducción: La colas de prioridad son un tema importante dentro de las ciencias de la computación. La busqueda de una implementacion que trabaje lo suficientemente rapido de una de estas estructuras es motivada principalmente por dos algoritmos de optimizacion en grafos, que son: algoritmo de Dijsktra: Camino más corto (SP, Shorter Path) y el algoritmo de Prim: árbol expandido minimal (MTS, Minimal Spanning Tree). Como se verá, Un Heap Fibonacci provee una rapida y elegante solucion a esto. Otras situaciones de interes en los que se usa esta estructura, son aquellas que el borrado del elemento minimo y de borrado de cualquier otro elemento son poco frecuentesen comparacion con el resto. Un Heap Fibonacci es una estructura de datos inventada por Fredman y Tarjan en 1984 que da una implementacion muy eficiente de las colas de prioridad. Un heap de Fibonacci es una estructura de datos similar a un heap binomial pero con mejor coste amortizado. La meta es encontrar un camino rapido a minimizar el numero de operaciones para calcular el MST o SP, debido a que se mejora el tiempo de ejecucion asintotico de ambos algoritmos. Las operaciones que más interesan para este caso son Insertar, Decrementar clave, Union y Encontrar Min, que trabajan con un tiempo constante amortizado. La meta para alcanzar este bajo coste de operaciones es crear operaciones 'peresozas' . Con esto, el programador es forzado a hacer varias operaciones menos costosas en orden O(), haciendo que la estructura sea compliacada. Las operaciones Borrar y Borrar el mínimo tienen un coste O(logn) como coste amortizado. Esto significa que, empezando con una estructura de datos vacía, cualquier secuencia de ‘a’ operaciones del primer grupo y ‘b’ operaciones del segundo grupo tardarían O(a + b.logn). En un heap ‘binomial’ esta secuencia de operaciones tardarían O((a+b)log(n)). Un heap de Fibonacci es mejor que un heap binomial cuando b es asintóticamente más pequeño que a. Aunque los costes son los arriba indicados, algunas operaciones pueden llevar mucho tiempo (en concreto Decrementar clave, Borrar y Borrar mínimo tienen un coste lineal en el peor caso). Por esta razón los Heaps de Fibonacci y otras estructuras de datos con coste amortizado no son apropiadas para sistemas de tiempo real.

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

Definición: Un Heap de Fibonacci es una colección de árboles que satisfacen la propiedad de Min-Heap, es decir, la clave de un hijo es siempre mayor o igual que la de su padre. Esto implica que la clave mínima está siempre en la raíz. Comparado con los Heaps binomiales, la estructura de un heap de Fibonacci es más flexible. Los árboles no tienen una forma predefinida y en un caso extremo el heap puede tener cada elemento en un árbol separado o en un único árbol de profundidad n. Esta flexibilidad permite que algunas operaciones puedan ser ejecutadas de una manera ‘perezosa’, posponiendo el trabajo para operaciones posteriores. Por ejemplo, la unión de dos Heaps se hace simplemente concatenando las dos listas de árboles, y la operación Decrementar clave a veces corta un nodo de su padre y forma un nuevo árbol. Sin embargo, se debe introducir algún orden para conseguir el tiempo de ejecución deseado. En concreto, el grado de los nodos(el número de hijos) se tiene que mantener bajo: cada nodo tiene un grado máximo de O(logn) y la talla de un subárbol cuya raíz tiene grado k es por lo menos Fk+2 , donde Fk es un número de Fibonacci (por eso el nombre que se les da a este tipo de heap. Esto se consigue con la regla de que podemos cortar como mucho un hijo de cada nodo no raíz. Cuando es cortado un segundo hijo, el nodo también necesita ser cortado de su padre y se convierte en la raíz de un nuevo árbol. El número de árboles se decrementa en la operación Borrar mínimo, donde los árboles están unidos entre sí. Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa. En el análisis del coste de ejecución amortizado pretendemos que las operaciones muy rápidas tarden un poco más de lo que tardan. Este tiempo extra se resta después al tiempo de ejecución de operaciones más lentas. La cantidad de tiempo ahorrada para un uso posterior es medida por una función potencial. Esta función es: Potencial =t 2∗m 

Donde t es el número de árboles en el Heap de Fibonacci, y m es el número de nodos marcados. Un nodo está marcado si al menos uno de sus hijos se cortó desde que el nodo se fue hecho hijo de otro nodo (todas las raíces están desmarcadas). Además, la raíz de cada árbol en un Heap tiene una unidad de tiempo almacenada. Esta unidad de tiempo puede ser usada más tarde para unir este árbol a otro con coste amortizado 0. Cada nodo marcado también tiene dos unidades de tiempo almacenadas. Una puede ser usada para cortar el nodo de su padre. Si esto sucede, el nodo se convierte en una raíz y la segunda unidad de tiempo se mantendrá almacenada como en cualquier otra raíz.

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

Operaciones:  Crear un Heap de Fibonacci vacío: 

Consta de dos operaciones:  M.min = nil //El puntero a la raiz mínima  M.n = 0 //El número de Nodos



El costo de esta operación es O(1)

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

3



Operación de inserción de un nuevo nodo:



Nótese que si se insertan k nodos consecutivos, la lista de raíces se incrementa con k árboles de un solo nodo (a diferencia de los montículos binomiales, en los que se hace un esfuerzo de compactación).



El costo de agregar cada nodo es de O(1)

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

4





Buscar el elemento de valor mínimo: 

El nodo de clave minima es precisamente el apuntado por M.min



El costo de esta operación es de O(1)

Unión de dos Heap de Fibonacci:



Tampoco hay compactación por lo que el coste es nuevamente O(1)

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

5



Borrar elemento con clave mínima:



La funcion 'concatenar' debe juntar las raices de igual grado hasta conseguir que haya como mucho una raiz de cada grado (asi se reduce en numero de arboles en el Heap), y ordena las raices por grado.

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

6



Para compactar, se repitenn los mismos pasos hasta que todas las raices de la lista de raices del heap tengan distinto grado. 

Buscar dos raices x e y que tengan igual grado y con la clave de x menor o igual que la clave de y.



Borrar y de la lista de raices y hacer que y sea hijo de x (función 'enlazar'). Se incrementa en grado de x y se pone x como no marcado.

 



Ahora el algoritmo 'compactar': 

Se utiliza un vector auxiliar A[0..D(n)], donde n es el numero de datos en el heap; A[i] = y significa que y en una raiz con grado i.

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

7



Veamos el procesamiento de cada raiz w:



Y ya solo queda reconstruir la lista de raices a partir de la informacion en el vector A.



Costo de la operación borrar minimo O(Log n)

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

8

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

9

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

11

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1



Decrecer valor de una clave: 

Vemos primero un subalgoritmo auxiliar:  Corta el enlace entre un nodo y su padre, convirtindo el hijo en raiz.



El algoritmo de reduccion de una clave:

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1



Caso 0:



Caso 1:

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

Caso 2:

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1



Borrar cualquier elemento del heap:



El algoritmo hace decrecer el valor de la clave del elemento a borrar con el valor minimo posible (- infinito).



Luego se borra ese elemento.

Implementacion: * FibonnaciHeap.java * -------------------------* (C) Copyright 1999-2003, by Nathan Fiedler and Contributors. * * Original Author: Nathan Fiedler * Contributor(s): John V. Sichi * * Changes * ------* 03-Sept-2003 : Adapted from Nathan Fiedler (JVS); * * Name Date Description * ---- -------------* nf 08/31/97 Initial version * nf 09/07/97 Removed FibHeapData interface * nf 01/20/01 Added synchronization * nf 01/21/01 Made Node an inner class * nf 01/05/02 Added clear(), renamed empty() to * isEmpty(), and renamed printHeap()

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

* to toString() * nf 01/06/02 Removed all synchronization * */ package fibonacciminheap; import java.util.*; * This class implements a Fibonacci heap data structure. Much of the code in * this class is based on the algorithms in the "Introduction to Algorithms"by * Cormen, Leiserson, and Rivest in Chapter 21. The amortized running time of * most of these methods is O(1), making it a very fast data structure. Several * have an actual running time of O(1). removeMin() and delete() have O(log n) * amortized running times because they do the heap consolidation. If you * attempt to store nodes in this heap with key values of -Infinity * (Double.NEGATIVE_INFINITY) the delete() operation may fail to * remove the correct element. * *

Note that this implementation is not synchronized. If multiple * threads access a set concurrently, and at least one of the threads modifies * the set, it must be synchronized externally. This is typically * accomplished by synchronizing on some object that naturally encapsulates the * set.

* *

This class was originally developed by Nathan Fiedler for the GraphMaker * project. It was imported to JGraphT with permission, courtesy of Nathan * Fiedler.

* * @author Nathan Fiedler */ public class FibonacciHeap { //~ Instance fields -------------------------------------------------------/** * Points to the minimum node in the heap. */ private FibonacciHeapNode minNode; /** * Number of nodes in the heap. */ private int nNodes; //~ Constructors ----------------------------------------------------------/** * Constructs a FibonacciHeap object that contains no elements. */ public FibonacciHeap() { } // FibonacciHeap //~ Methods ---------------------------------------------------------------/** * Tests if the Fibonacci heap is empty or not. Returns true if the heap is * empty, false otherwise. * *

Running time: O(1) actual

*

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

* @return true if the heap is empty, false otherwise */ public boolean isEmpty() { return minNode == null; } // isEmpty /** * Removes all elements from this heap. */ public void clear() { minNode = null; nNodes = 0; } // clear /** * Decreases the key value for a heap node, given the new value to take on. * The structure of the heap may be changed and will not be consolidated. * *

Running time: O(1) amortized

* * @param x node to decrease the key of * @param k new key value for node x * * @exception IllegalArgumentException Thrown if k is larger than x.key * value. */ public void decreaseKey(FibonacciHeapNode x, Comparable k) { if (k.compareTo(x.key)>0) { //Si es menor el numero nuevo throw new IllegalArgumentException( "decreaseKey() got larger key value"); } x.key = k; FibonacciHeapNode y = x.parent; if ((y != null) && (x.key.compareTo(y.key)<0)) { cut(x, y); cascadingCut(y); } if (x.key.compareTo( minNode.key)<0) { minNode = x; } } // decreaseKey /** * Deletes a node from the heap given the reference to the node. The trees * in the heap will be consolidated, if necessary. This operation may fail * to remove the correct element if there are nodes with key value * -Infinity. * *

Running time: O(log n) amortized

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

* * @param x node to remove from heap */ public void delete(FibonacciHeapNode x) { // make x as small as possible decreaseKey(x, Double.NEGATIVE_INFINITY); // remove the smallest, which decreases n also removeMin(); } // delete /** * Inserts a new data element into the heap. No heap consolidation is * performed at this time, the new node is simply inserted into the root * list of this heap. * *

Running time: O(1) actual

* * @param node new node to insert into heap * @param key key value associated with data object */ public void insert(FibonacciHeapNode node, Comparable key) { node.key = key; Comparable key = node.key; // concatenate node into min list if (minNode != null) { node.left = minNode; node.right = minNode.right; minNode.right = node; node.right.left = node; if (key.compareTo( minNode.key)<0) { minNode = node; } } else { minNode = node; } nNodes++; } // insert /** * Returns the smallest element in the heap. This smallest element is the * one with the minimum key value. * *

Running time: O(1) actual

* * @return heap node with the smallest key */ public FibonacciHeapNode min() { return minNode; } // min

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

/** * Removes the smallest element from the heap. This will cause the trees in * the heap to be consolidated, if necessary. * *

Running time: O(log n) amortized

* * @return node with the smallest key */ public FibonacciHeapNode removeMin() { FibonacciHeapNode z = minNode; if (z != null) { int numKids = z.degree; FibonacciHeapNode x = z.child; FibonacciHeapNode tempRight; // for each child of z do... while (numKids > 0) { tempRight = x.right; // remove x from child list x.left.right = x.right; x.right.left = x.left; // add x to root list of heap x.left = minNode; x.right = minNode.right; minNode.right = x; x.right.left = x; // set parent[x] to null x.parent = null; x = tempRight; numKids--; } // remove z from root list of heap z.left.right = z.right; z.right.left = z.left; if (z == z.right) { minNode = null; } else { minNode = z.right; consolidate(); } // decrement size of heap nNodes--; } return z; } // removeMin /** * Returns the size of the heap which is measured in the number of elements * contained in the heap. * *

Running time: O(1) actual

*

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

* @return number of elements in the heap */ public int size() { return nNodes; } // size /** * Joins two Fibonacci heaps into a new one. No heap consolidation is * performed at this time. The two root lists are simply joined together. * *

Running time: O(1) actual

* * @param h1 first heap * @param h2 second heap * * @return new heap containing h1 and h2 */ public static FibonacciHeap union( FibonacciHeap h1, FibonacciHeap h2) { FibonacciHeap h = new FibonacciHeap(); if ((h1 != null) && (h2 != null)) { h.minNode = h1.minNode; if (h.minNode != null) { if (h2.minNode != null) { h.minNode.right.left = h2.minNode.left; h2.minNode.left.right = h.minNode.right; h.minNode.right = h2.minNode; h2.minNode.left = h.minNode; if (h2.minNode.key.compareTo(h1.minNode.key)<0) { h.minNode = h2.minNode; } } } else { h.minNode = h2.minNode; } h.nNodes = h1.nNodes + h2.nNodes; } return h; } // union /** * Creates a String representation of this Fibonacci heap. * * @return String of this. */ public String toString() { if (minNode == null) { return "FibonacciHeap=[]"; }

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

// create a new stack and put root on it Stack> stack = new Stack>(); stack.push(minNode); StringBuffer buf = new StringBuffer(512); buf.append("FibonacciHeap=["); // do a simple breadth-first traversal on the tree while (!stack.empty()) { FibonacciHeapNode curr = stack.pop(); buf.append(curr); buf.append(", "); if (curr.child != null) { stack.push(curr.child); } FibonacciHeapNode start = curr; curr = curr.right; while (curr != start) { buf.append(curr); buf.append(", "); if (curr.child != null) { stack.push(curr.child); } curr = curr.right; } } buf.append(']'); return buf.toString(); } // toString /** * Performs a cascading cut operation. This cuts y from its parent and then * does the same for its parent, and so on up the tree. * *

Running time: O(log n); O(1) excluding the recursion

* * @param y node to perform cascading cut on */ protected void cascadingCut(FibonacciHeapNode y) { FibonacciHeapNode z = y.parent; // if there's a parent... if (z != null) { // if y is unmarked, set it marked if (!y.mark) { y.mark = true; } else { // it's marked, cut it from parent cut(y, z); // cut its parent as well cascadingCut(z);

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

} } } // cascadingCut /** * Consolidates the trees in the heap by joining trees of equal degree until * there are no more trees of equal degree in the root list. * *

Running time: O(log n) amortized

*/ protected void consolidate() { int arraySize = nNodes + 1; List> array = new ArrayList>(arraySize); // Initialize degree array for (int i = 0; i < arraySize; i++) { array.add(null); } // Find the number of root nodes. int numRoots = 0; FibonacciHeapNode x = minNode; if (x != null) { numRoots++; x = x.right; while (x != minNode) { numRoots++; x = x.right; } } // For each node in root list do... while (numRoots > 0) { // Access this node's degree.. int d = x.degree; FibonacciHeapNode next = x.right; // ..and see if there's another of the same degree. while (array.get(d) != null) { // There is, make one of the nodes a child of the other. FibonacciHeapNode y = array.get(d); // Do this based on the key value. if (x.key.compareTo( y.key)>0) { FibonacciHeapNode temp = y; y = x; x = temp; } // FibonacciHeapNode y disappears from root list. link(y, x); // We've handled this degree, go to next one. array.set(d, null); d++; }

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

// Save this node for later when we might encounter another // of the same degree. array.set(d, x); // Move forward through list. x = next; numRoots--; } // Set min to null (effectively losing the root list) and // reconstruct the root list from the array entries in array[]. minNode = null; for (int i = 0; i < arraySize; i++) { if (array.get(i) != null) { // We've got a live one, add it to root list. if (minNode != null) { // First remove node from root list. array.get(i).left.right = array.get(i).right; array.get(i).right.left = array.get(i).left; // Now add to root list, again. array.get(i).left = minNode; array.get(i).right = minNode.right; minNode.right = array.get(i); array.get(i).right.left = array.get(i); // Check if this is a new min. if (array.get(i).key.compareTo(minNode.key)<0) { minNode = array.get(i); } } else { minNode = array.get(i); } } } } // consolidate /** * The reverse of the link operation: removes x from the child list of y. * This method assumes that min is non-null. * *

Running time: O(1)

* * @param x child of y to be removed from y's child list * @param y parent of x about to lose a child */ protected void cut(FibonacciHeapNode x, FibonacciHeapNode y) { // remove x from childlist of y and decrement degree[y] x.left.right = x.right; x.right.left = x.left; y.degree--; // reset y.child if necessary if (y.child == x) { y.child = x.right; } if (y.degree == 0) { y.child = null;

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

} // add x to root list of heap x.left = minNode; x.right = minNode.right; minNode.right = x; x.right.left = x; // set parent[x] to nil x.parent = null; // set mark[x] to false x.mark = false; } // cut /** * Make node y a child of node x. * *

Running time: O(1) actual

* * @param y node to become child * @param x node to become parent */ protected void link(FibonacciHeapNode y, FibonacciHeapNode x) { // remove y from root list of heap y.left.right = y.right; y.right.left = y.left; // make y a child of x y.parent = x; if (x.child == null) { x.child = y; y.right = y; y.left = y; } else { y.left = x.child; y.right = x.child.right; x.child.right = y; y.right.left = y; } // increase degree[x] x.degree++; // set mark[y] false y.mark = false; } // link } // FibonacciHeap /* -------------------------* FibonnaciHeapNode.java * -------------------------* (C) Copyright 1999-2006, by Nathan Fiedler and Contributors. *

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

* Original Author: Nathan Fiedler * Contributor(s): John V. Sichi * * $Id: FibonacciHeapNode.java 536 2007-03-20 21:57:52Z perfecthash $ * * Changes * ------* 03-Sept-2003 : Adapted from Nathan Fiedler (JVS); * * Name Date Description * ---- -------------* nf 08/31/97 Initial version * nf 09/07/97 Removed FibHeapData interface * nf 01/20/01 Added synchronization * nf 01/21/01 Made Node an inner class * nf 01/05/02 Added clear(), renamed empty() to * isEmpty(), and renamed printHeap() * to toString() * nf 01/06/02 Removed all synchronization * JVS 06/24/06 Generics * */ package fibonacciminheap; /** * Implements a node of the Fibonacci heap. It holds the information necessary * for maintaining the structure of the heap. It also holds the reference to the * key value (which is used to determine the heap structure). * * @author Nathan Fiedler */ public class FibonacciHeapNode { //~ Instance fields -------------------------------------------------------/** * Node data. */ T data; /** * first child node */ FibonacciHeapNode child; /** * left sibling node */ FibonacciHeapNode left; /** * parent node */ FibonacciHeapNode parent; /** * right sibling node */ FibonacciHeapNode right; /** * true if this node has had a child removed since this node was added to * its parent

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

*/ boolean mark; /** * key value for this node */ Comparable key; /** * number of children of this node (does not count grandchildren) */ int degree; //~ Constructors ----------------------------------------------------------/** * Default constructor. Initializes the right and left pointers, making this * a circular doubly-linked list. * * @param data data for this node * @param key initial key for node */ public FibonacciHeapNode(T data, Comparable key) { right = this; left = this; this.data = data; this.key = key; } //~ Methods ---------------------------------------------------------------/** * Obtain the key for this node. * * @return the key */ public final Comparable getKey() { return key; } /** * Obtain the data for this node. */ public final T getData() { return data; } /** * Return the string representation of this object. * * @return string representing this object */ public String toString() { if (true) { return key.toString(); } else { StringBuffer buf = new StringBuffer(); buf.append("Node=[parent = ");

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

if (parent != null) { buf.append(parent.key); } else { buf.append("---"); } buf.append(", key = "); buf.append(key); buf.append(", degree = "); buf.append(Integer.toString(degree)); buf.append(", right = "); if (right != null) { buf.append(right.key); } else { buf.append("---"); } buf.append(", left = "); if (left != null) { buf.append(left.key); } else { buf.append("---"); } buf.append(", child = "); if (child != null) { buf.append(child.key); } else { buf.append("---"); } buf.append(']'); return buf.toString(); } } // toString } // End FibonacciHeapNode.java /* * Main.java * * Created on 4 de julio de 2008, 20:38 * * To change this template, choose Tools | Template Manager * and open the template in the editor. */ package fibonacciminheap; /** * * @author Abel O'Rian */

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

2

public class Main { /** Creates a new instance of Main */ public Main() { } /** * @param args the command line arguments */ public static void main(String[] args) { FibonacciHeap fh = new FibonacciHeap(); FibonacciHeapNode nodo; for (int i=0; i<15; i++){ nodo = new FibonacciHeapNode("dato",5); fh.insert(nodo,15-i); } System.out.println(fh.toString()); System.out.println("Raiz: "+ fh.min().key); fh.removeMin(); System.out.println(fh.toString()); for (int i=0; i<14; i++){ System.out.println("Minimo: "+fh.removeMin().key); } } }

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

3