FiboHeap.hpp

Go to the documentation of this file.

/****************************************************************
 * DATA.HPP
 * 
 * This file contains the implementation of a Fibonacci Heap
 * data structure, necessary for an efficient Dijkstra algorithm
 * implementation.
 * 
 * Authors: Erel Segal - modified by J. Barthelemy
 * Date   : 15 august 2013
 ****************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef unsigned int uint;



template <typename Data, typename Key> class FibonacciHeapNode {
  
  Key myKey;   
  Data myData; 

  uint degree; 
  bool mark;   

  // pointers in a circular doubly linked list
  FibonacciHeapNode<Data,Key>* previous;  
  FibonacciHeapNode<Data,Key>* next;      
  FibonacciHeapNode<Data,Key>* child;     
  FibonacciHeapNode<Data,Key>* parent;    

  FibonacciHeapNode():
    myKey(-1),
    myData(NULL),
    degree(0),
    mark(false),
    child(NULL),
    parent(NULL) {
    previous = next = this; // doubly linked circular list
  }


  FibonacciHeapNode(Data d, Key k):
    myKey(k),
    myData(d),
    degree(0),
    mark(false),
    child(NULL),
    parent(NULL) {
    previous = next = this; // doubly linked circular list
  }


  bool isSingle() const {
    return (this == this->next);
  }


  void insert(FibonacciHeapNode<Data,Key>* other) {

    if (!other) return;

    this->next->previous = other->previous;
    other->previous->next = this->next;

    this->next = other;
    other->previous = this;

  }

  void remove() {
    this->previous->next = this->next;
    this->next->previous = this->previous;
    this->next = this->previous = this;
  }


  void addChild(FibonacciHeapNode<Data,Key>* other) {
    if (!child)
      child = other;
    else
      child->insert(other);
    other->parent = this;
    other->mark = false;
    degree++;
    //count += other->count;
  }


  void removeChild(FibonacciHeapNode<Data,Key>* other) {
    if (other->parent!=this)
      throw string ("Trying to remove a child from a non-parent");
    if (other->isSingle()) {
      if (child != other)
        throw string ("Trying to remove a non-child");
      child = NULL;
    } else {
      if (child == other)
        child = other->next;
      other->remove(); // from list of children
    }
    other->parent=NULL;
    other->mark = false;
    degree--;
    //count -= other->count;
  }



  friend ostream& operator<< (ostream& out, const FibonacciHeapNode& n) {
    return (out << n.myData << ":" << n.myKey);
  }


  void printTree(ostream& out) const {
    out << myData << ":" << myKey << ":" << degree << ":" << mark;
    if (child) {
      out << "(";
      const FibonacciHeapNode<Data,Key>* n=child;
      do {
        if (n==this)
          throw string("Illegal pointer - node is child of itself");
        n->printTree(out);
        out << " ";
        n = n->next;
      } while (n!=child);
      out << ")";
    }
  }


  void printAll(ostream& out) const {
    const FibonacciHeapNode<Data,Key>* n=this;
    do {
      n->printTree(out);
      out << " ";
      n = n->next;
    } while (n!=this);
    out << endl;
  }

public:


  Key key() const { return myKey; }


  Data data() const { return myData; }

  template <typename D, typename K> friend class FibonacciHeap;
};



template <typename Data, typename Key> class FibonacciHeap {

  typedef FibonacciHeapNode<Data,Key>* PNode;

  PNode rootWithMinKey; 
  uint count;           
  uint maxDegree;       

protected:


  PNode insertNode(PNode newNode) {

    if (!rootWithMinKey) { // insert the first myKey to the heap:
      rootWithMinKey = newNode;
    } else {
      rootWithMinKey->insert(newNode);  // insert the root of new tree to the list of roots
      if (newNode->key() < rootWithMinKey->key())  rootWithMinKey = newNode;
    }

    return newNode;

  }

public:

  FibonacciHeap():
    rootWithMinKey(NULL), count(0), maxDegree(0) {}

  ~FibonacciHeap() {

    while(this->empty() == false ) {
      deletemin();
    }

  }


  bool empty() const {return count==0;}


  PNode minimum() const {
    if (!rootWithMinKey)
      throw string("no minimum element");
    return rootWithMinKey;
  }


  void printRoots(ostream& out) const {
    out << "maxDegree=" << maxDegree << "  count=" << count << "  roots=";
    if (rootWithMinKey)
      rootWithMinKey->printAll(out);
    else
      out << endl;
  }
  

  void merge (const FibonacciHeap& other) {  
    rootWithMinKey->insert(other.rootWithMinKey);
    if (!rootWithMinKey || (other.rootWithMinKey && other.rootWithMinKey->key() < rootWithMinKey->key()))
      this->rootWithMinKey = other.rootWithMinKey;
    count += other.count;
  }


  PNode insert (Data d, Key k) {
    count++;
    // create a new tree with a single myKey:
    return insertNode(new FibonacciHeapNode<Data,Key>(d,k));
  }

  void deletemin() {  
    if (!rootWithMinKey) throw string("trying to remove from an empty heap");
    count--;

    // Make all children of root new roots:
    if (rootWithMinKey->child) {

      PNode c = rootWithMinKey->child;

      do {

        c->parent = NULL;
        c = c->next;

      } while (c!=rootWithMinKey->child);

      rootWithMinKey->child = NULL; // removed all children
      rootWithMinKey->insert(c);

    }

    if (rootWithMinKey->next == rootWithMinKey) {

      if (count!=0) throw string ("Internal error: should have 0 keys");
      rootWithMinKey = NULL;
      return;

    }

    vector<PNode> degreeRoots ((maxDegree+250)); // make room for a new degree
    fill (degreeRoots.begin(), degreeRoots.end(), (PNode)NULL);
    maxDegree = 0;
    PNode currentPointer = rootWithMinKey->next;
    uint currentDegree;
    do {

      currentDegree = currentPointer->degree;

      PNode current = currentPointer;
      currentPointer = currentPointer->next;
      while (degreeRoots[currentDegree] != NULL) { // merge the two roots with the same degree:
        PNode other = degreeRoots[currentDegree]; // another root with the same degree
        if (current->key() > other->key())
          swap(other,current);
        // now current->key() <= other->key() - make other a child of current:
        other->remove(); // remove from list of roots
        current->addChild(other);

        degreeRoots[currentDegree]=NULL;
        currentDegree++;
        if (currentDegree >= degreeRoots.size())
          degreeRoots.push_back((PNode)NULL);
      }
      // keep the current root as the first of its degree in the degrees array:
      degreeRoots[currentDegree] = current;

    } while (currentPointer != rootWithMinKey);

    delete rootWithMinKey;
    rootWithMinKey = NULL;

    unsigned int newMaxDegree=0;
    for (unsigned int d=0; d<degreeRoots.size(); ++d) {
      if (degreeRoots[d]) {
        degreeRoots[d]->next = degreeRoots[d]->previous = degreeRoots[d];
        insertNode(degreeRoots[d]);
        if (d>newMaxDegree)
          newMaxDegree = d;
      }
    }
    maxDegree=newMaxDegree;

  }


  void decreaseKey(PNode node, Key newKey) {

    if (newKey >= node->myKey)
      throw string("Trying to decrease key to a greater key");

    // Update the key and possibly the min key:
    node->myKey = newKey;

    // Check if the new key violates the heap invariant:
    PNode parent = node->parent;

    if (parent == NULL ) { // root node - just make sure the minimum is correct
      if (newKey < rootWithMinKey->key())
        rootWithMinKey = node;
      return; // heap invariant not violated - nothing more to do
    } else if (parent->key() <= newKey) {
      return; // heap invariant not violated - nothing more to do
    }

    for(;;) {
      parent->removeChild(node);
      insertNode(node);

      if (!parent->parent) { // parent is a root - nothing more to do
        break;
      } else if (!parent->mark) {  // parent is not a root and is not marked - just mark it
        parent->mark = true;
        break;
      } else {
        node = parent;
        parent = parent->parent;
        continue;
      }
    };
  }


  void remove(PNode node, Key minusInfinity) {
    if (minusInfinity >= minimum()->key())
      throw string("2nd argument to remove must be a key that is smaller than all other keys");
    decreaseKey(node, minusInfinity);
    deletemin();
  }

};