Changeset 8572


Ignore:
Timestamp:
09/04/12 18:26:40 (7 years ago)
Author:
spimming
Message:

#1894: FibonacciHeap implementation added

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs

    r8546 r8572  
    11using System;
     2using System.Collections.Generic;
    23using HeuristicLab.Algorithms.GraphRouting.Interfaces;
    34
     
    78    where V : IComparable {
    89
     10    private HeapNode min;
     11    private int size;
    912
    1013    public int Size {
    11       get { throw new NotImplementedException(); }
     14      get { return size; }
    1215    }
    1316
    14     public System.Collections.Generic.KeyValuePair<K, V> PeekMin() {
    15       throw new NotImplementedException();
     17    public FibonacciHeap() {
     18      size = 0;
     19      min = null;
     20    }
     21
     22    public KeyValuePair<K, V> PeekMin() {
     23      if (size == 0) {
     24        throw new InvalidOperationException("Heap is empty");
     25      }
     26      KeyValuePair<K, V> pair = new KeyValuePair<K, V>(min.Key, min.Value);
     27      return pair;
    1628    }
    1729
    1830    public K PeekMinKey() {
    19       throw new NotImplementedException();
     31      if (size == 0) {
     32        throw new InvalidOperationException("Heap is empty");
     33      }
     34      return min.Key;
    2035    }
    2136
    2237    public V PeekMinValue() {
    23       throw new NotImplementedException();
     38      if (size == 0) {
     39        throw new InvalidOperationException("Heap is empty");
     40      }
     41      return min.Value;
    2442    }
    2543
    2644    public void Insert(K key, V value) {
    27       throw new NotImplementedException();
     45      HeapNode n = new HeapNode(key, value);
     46      if (min == null) {
     47        min = n;
     48      } else {
     49        n.Right = min;
     50        n.Left = min.Left;
     51        n.Right.Left = n;
     52        n.Left.Right = n;
     53        if (n.Key.CompareTo(min.Key) < 0) {
     54          min = n;
     55        }
     56      }
     57      size++;
    2858    }
    2959
     
    3363
    3464    public void RemoveMin() {
    35       throw new NotImplementedException();
     65      if (size == 0) {
     66        throw new InvalidOperationException("Heap is empty");
     67      }
     68      HeapNode z = min;
     69      if (z.Child != null) {
     70        // set all z's childs parent to null ...
     71        z.Child.Parent = null;
     72        HeapNode x = z.Child.Right;
     73        while (x != z.Child) {
     74          x.Parent = null;
     75          x = x.Right;
     76        }
     77        // ... and make all of them roots
     78        HeapNode minLeft = min.Left;
     79        min.Left = z.Child.Left;
     80        min.Left.Right = min;
     81        z.Child.Left = minLeft;
     82        minLeft.Right = z.Child;
     83      }
     84
     85      // remove z frome root list
     86      z.Left.Right = z.Right;
     87      z.Right.Left = z.Left;
     88
     89      if (z == z.Right) {
     90        min = null;
     91      } else {
     92        // point min to a node other than z
     93        // (not necessarily going to be the new minimum)
     94        min = z.Right;
     95        Consolidate();
     96      }
     97      size--;
     98
     99      //var zNode = new KeyValuePair<K, V>(z.Key, z.Value);
     100      z = null;
     101      //return zNode;
     102    }
     103
     104    private void Link(HeapNode y, HeapNode z) {
     105      y.Left.Right = y.Right;
     106      y.Right.Left = y.Left;
     107
     108      y.Parent = z;
     109      if (z.Child == null) {
     110        z.Child = y;
     111        y.Right = y;
     112        y.Left = y;
     113      } else {
     114        y.Left = z.Child;
     115        y.Right = z.Child.Right;
     116        z.Child.Right = y;
     117        y.Right.Left = y;
     118      }
     119      z.Degree++;
     120      y.Mark = false;
     121    }
     122
     123    private void Consolidate() {
     124      //TODO: explain magic number
     125      HeapNode[] A = new HeapNode[45];
     126      HeapNode start = min;
     127      HeapNode w = min;
     128
     129      do {
     130        HeapNode x = w;
     131        HeapNode nextW = w.Right;
     132        int d = x.Degree;
     133
     134        while (A[d] != null) {
     135          HeapNode y = A[d];     // another node with the same degree as x
     136          if (x.Key.CompareTo(y.Key) > 0) {
     137            // exchange x <-> y
     138            HeapNode tmp = x;
     139            x = y;
     140            y = tmp;
     141          }
     142          if (y == start) {
     143            start = start.Right;
     144          }
     145          if (y == nextW) {
     146            nextW = nextW.Right;
     147          }
     148          Link(y, x);
     149          A[d] = null;
     150          d++;
     151        }
     152
     153        A[d] = x;
     154        w = nextW;
     155      } while (w != start);
     156
     157      min = null;
     158
     159      for (int i = 0; i < 45; i++) {
     160        if (A[i] != null) {
     161          HeapNode n = A[i];
     162          if (min == null) {
     163            min = n;
     164          } else {
     165            if (n.Key.CompareTo(min.Key) < 0) {
     166              min = n;
     167            }
     168          }
     169        }
     170      }
     171    }
     172
     173    private class HeapNode {
     174      public K Key;
     175      public V Value;
     176      public int Degree;
     177      public bool Mark;
     178      public HeapNode Left;
     179      public HeapNode Right;
     180      public HeapNode Parent;
     181      public HeapNode Child;
     182
     183      public HeapNode(K key, V value) {
     184        this.Key = key;
     185        this.Value = value;
     186        this.Right = this;
     187        this.Left = this;
     188        this.Parent = null;
     189        this.Child = null;
     190        this.Degree = 0;
     191        this.Mark = false;
     192      }
    36193    }
    37194  }
Note: See TracChangeset for help on using the changeset viewer.