Free cookie consent management tool by TermsFeed Policy Generator

source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/Heap4.cs @ 8546

Last change on this file since 8546 was 8546, checked in by spimming, 10 years ago

#1894:

  • fast binary heap added
  • 4-ary binary heap added
  • FibonacciHeap initial commit
File size: 5.5 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using HeuristicLab.Algorithms.GraphRouting.Interfaces;
5namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
6  // implementation based on C++ version from Peter Sanders
7  // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
8  public sealed class Heap4<K, V> : IHeap<K, V> where K : IComparable {
9    private class KNElement {
10      public K Key { get; set; }
11      public V Value { get; set; }
12    }
13
14    private int capacity;
15    private K supremum;
16    private int size; // index of last used element
17    private int finalLayerSize; // size of first layer with free space
18    private int finalLayerDist; // distance to end of layer
19    //private KNElement[] rawData;
20    private KNElement[] data;    // alligned version of rawData
21
22    public Heap4(K sup, K infimum, int cap) {
23      capacity = cap;
24      supremum = sup;
25      data = new KNElement[capacity + 4];
26
27      for (int i = 0; i < capacity + 4; i++) {
28        data[i] = new KNElement();
29      }
30
31      data[0].Key = infimum; // sentinel
32      data[capacity + 1].Key = supremum;
33      data[capacity + 2].Key = supremum;
34      data[capacity + 3].Key = supremum;
35      Reset();
36    }
37
38    public int Size {
39      get { return size; }
40    }
41
42    public K Supremum {
43      get { return data[capacity + 1].Key; }
44    }
45
46    public KeyValuePair<K, V> PeekMin() {
47      if (size == 0) {
48        throw new InvalidOperationException("Heap is empty");
49      }
50      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
51    }
52
53    public K PeekMinKey() {
54      return data[1].Key;
55    }
56
57    public V PeekMinValue() {
58      return data[1].Value;
59    }
60
61    public void RemoveMin() {
62      K minKey;
63      K otherKey;
64      int delta;
65
66      // first move up elements on a min-path
67      int hole = 1;
68      int succ = 2;
69      int layerSize = 4;
70      int layerPos = 0;
71      int sz = size;
72      size = sz - 1;
73      finalLayerDist++;
74      if (finalLayerDist == finalLayerSize) {
75        finalLayerSize >>= 2;
76        finalLayerDist = 0;
77      }
78
79      while (succ < sz) {
80        minKey = data[succ].Key;
81        delta = 0;
82
83        otherKey = data[succ + 1].Key;
84        if (otherKey.CompareTo(minKey) < 0) {
85          minKey = otherKey;
86          delta = 1;
87        }
88        otherKey = data[succ + 2].Key;
89        if (otherKey.CompareTo(minKey) < 0) {
90          minKey = otherKey;
91          delta = 2;
92        }
93        otherKey = data[succ + 3].Key;
94        if (otherKey.CompareTo(minKey) < 0) {
95          minKey = otherKey;
96          delta = 3;
97        }
98        succ += delta;
99        layerPos += delta;
100
101        // move min successor up
102        data[hole].Key = minKey;
103        data[hole].Value = data[succ].Value;
104
105        // step to next layer
106        hole = succ;
107        succ = succ - layerPos + layerSize; // beginning of next layer
108        layerPos <<= 2;
109        succ += layerPos; // now correct value
110        layerSize <<= 2;
111      }
112
113      // bubble up rightmost element
114      K bubble = data[sz].Key;
115      layerSize >>= 2; // now size of hole's layer
116      layerPos >>= 2; // now pos of hole within its layer
117
118      int layerDist = layerSize - layerPos - 1; // hole's dist to end of layer
119      int pred = hole + layerDist - layerSize; // end of pred's layer for now
120      layerSize >>= 2; // now size of pred's layer
121      layerDist >>= 2; // now pred's pos in layer
122      pred = pred - layerDist; // finally preds index
123
124      while (data[pred].Key.CompareTo(bubble) > 0) {  // must terminate since inf at root
125        data[hole].Key = data[pred].Key;
126        data[hole].Value = data[pred].Value;
127        hole = pred;
128        pred = hole + layerDist - layerSize; // end of hole's layer for now
129        layerSize >>= 2;
130        layerDist >>= 2;
131        pred = pred - layerDist; // finally preds index
132      }
133
134      // finally move data to hole
135      data[hole].Key = bubble;
136      data[hole].Value = data[sz].Value;
137
138      data[sz].Key = Supremum; // mark as deleted
139    }
140
141    public void Insert(K key, V value) {
142      int layerSize = finalLayerSize;
143      int layerDist = finalLayerDist;
144      finalLayerDist--;
145
146      if (finalLayerDist == -1) { // layer full
147        // start next layer
148        finalLayerSize <<= 2;
149        finalLayerDist = finalLayerSize - 1;
150      }
151
152      size++;
153
154      int hole = size;
155      int pred = hole + layerDist - layerSize; // end of pred's layer for now
156      layerSize >>= 2; // now size of pred's layer
157      layerDist >>= 2;
158      pred = pred - layerDist; // finally preds index
159      K predKey = data[pred].Key;
160      while (predKey.CompareTo(key) > 0) {
161        data[hole].Key = predKey;
162        data[hole].Value = data[pred].Value;
163        hole = pred;
164        pred = hole + layerDist - layerSize; // end of pred's layer for now
165        layerSize >>= 2; // now isze of pred's layer
166        layerDist >>= 2;
167        pred = pred - layerDist; // finally preds index
168        predKey = data[pred].Key;
169      }
170
171      // finally move data to hole
172      data[hole].Key = key;
173      data[hole].Value = value;
174    }
175
176    public void DecreaseKey(K key, V value) {
177      throw new NotImplementedException();
178    }
179
180    // reset size to 0 and fill data array with sentinels
181    private void Reset() {
182      size = 0;
183      finalLayerSize = 1;
184      finalLayerDist = 0;
185      K sup = Supremum;
186      int cap = capacity;
187      for (int i = 1; i <= cap; i++) {
188        data[i].Key = sup;
189      }
190    }
191  }
192}
Note: See TracBrowser for help on using the repository browser.