source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs @ 8527

Last change on this file since 8527 was 8527, checked in by spimming, 7 years ago

#1894:

  • introduced heap interface
  • various heap implementation used as priority queues
  • very simple logger added
  • various versions of Astar algorithm
File size: 2.7 KB
Line 
1
2using System;
3namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
4  // implementation based on C++ version from Peter Sanders
5  // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
6  public sealed class BinaryHeap<K, V> where K : IComparable {
7    private class KNElement {
8      public K Key { get; set; }
9      public V Value { get; set; }
10    }
11
12    private int capacity;
13    private K supremum;
14    private int size; // index of last used element
15    private KNElement[] data;
16
17    public BinaryHeap(K sup, K infimum, int cap) {
18      size = 0;
19      capacity = cap;
20      data = new KNElement[cap + 2];
21      for (int i = 0; i < cap + 2; i++) {
22        data[i] = new KNElement();
23      }
24      data[0].Key = infimum; // sentinel
25      data[capacity + 1].Key = sup;
26      supremum = sup;
27      Reset();
28
29    }
30
31    public int Size {
32      get { return size; }
33    }
34
35    public K PeekMinKey() {
36      return data[1].Key;
37    }
38
39    public V PeekMinValue() {
40      return data[1].Value;
41    }
42
43    public void RemoveMin() {
44      int i;
45      int l;
46      int r;
47      int smallest;
48
49      if (size <= 0) {
50        throw new InvalidOperationException("Cannot delete on an empty queue");
51      }
52
53      data[1] = data[size];
54      data[size].Key = supremum;
55      size--;
56      i = 1;
57      for (; ; ) {
58        l = (i << 1);
59        r = (i << 1) + 1;
60        if ((l <= size) && (data[l].Key.CompareTo(data[i].Key) == -1)) {
61          smallest = l;
62        } else {
63          smallest = i;
64        }
65        if ((r <= size) && (data[r].Key.CompareTo(data[smallest].Key) == -1)) {
66          smallest = r;
67        }
68        if (smallest == i) break;
69        KNElement temp = data[i];
70        data[i] = data[smallest];
71        data[smallest] = temp;
72        i = smallest;
73      }
74    }
75
76    public void Insert(K key, V value) {
77      size++;
78      int hole = size;
79      while ((hole > 1) && (data[hole >> 1].Key.CompareTo(key) == 1)) {
80        data[hole] = data[hole >> 1];
81        hole = hole >> 1;
82      }
83      data[hole].Key = key;
84      data[hole].Value = value;
85    }
86
87    public void DecreaseKey(K key, V value) {
88      int pos = size;
89      while ((pos > 1) && (data[pos >> 1].Key.CompareTo(key) != 0)) {
90        pos = pos >> 1;
91      }
92      if (data[pos].Key.CompareTo(key) != 0) {
93        throw new InvalidOperationException("Key not found");
94      }
95      throw new NotImplementedException();
96    }
97
98
99
100    // reset size to 0 and fill data array with sentinels
101    private void Reset() {
102      size = 0;
103      K sup = supremum;
104      int cap = capacity;
105      for (int i = 1; i <= cap; i++) {
106        data[i].Key = sup;
107      }
108    }
109  }
110}
Note: See TracBrowser for help on using the repository browser.