Free cookie consent management tool by TermsFeed Policy Generator

source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs @ 8572

Last change on this file since 8572 was 8572, checked in by spimming, 12 years ago

#1894: FibonacciHeap implementation added

File size: 4.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using HeuristicLab.Algorithms.GraphRouting.Interfaces;
4
5namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
6  public sealed class FibonacciHeap<K, V> : IHeap<K, V>
7    where K : IComparable
8    where V : IComparable {
9
10    private HeapNode min;
11    private int size;
12
13    public int Size {
14      get { return size; }
15    }
16
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;
28    }
29
30    public K PeekMinKey() {
31      if (size == 0) {
32        throw new InvalidOperationException("Heap is empty");
33      }
34      return min.Key;
35    }
36
37    public V PeekMinValue() {
38      if (size == 0) {
39        throw new InvalidOperationException("Heap is empty");
40      }
41      return min.Value;
42    }
43
44    public void Insert(K key, V value) {
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++;
58    }
59
60    public void DecreaseKey(K key, V value) {
61      throw new NotImplementedException();
62    }
63
64    public void RemoveMin() {
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      }
193    }
194  }
195}
Note: See TracBrowser for help on using the repository browser.