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

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

#1894:

  • Dijkstra version with no decrease key
  • used wrong index in BinHeap implementation
  • implement interface in BinaryHeap
File size: 3.0 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 BinaryHeap<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 KNElement[] data;
18
19    public BinaryHeap(K sup, K infimum, int cap) {
20      size = 0;
21      capacity = cap;
22      data = new KNElement[cap + 2];
23      for (int i = 0; i < cap + 2; i++) {
24        data[i] = new KNElement();
25      }
26      data[0].Key = infimum; // sentinel
27      data[capacity + 1].Key = sup;
28      supremum = sup;
29      Reset();
30
31    }
32
33    public int Size {
34      get { return size; }
35    }
36
37    public KeyValuePair<K, V> PeekMin() {
38      if (size == 0) {
39        throw new InvalidOperationException("Heap is empty");
40      }
41      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
42    }
43
44    public K PeekMinKey() {
45      return data[1].Key;
46    }
47
48    public V PeekMinValue() {
49      return data[1].Value;
50    }
51
52    public void RemoveMin() {
53      int i;
54      int l;
55      int r;
56      int smallest;
57
58      if (size <= 0) {
59        throw new InvalidOperationException("Cannot delete on an empty queue");
60      }
61
62      data[1] = data[size];
63      data[size].Key = supremum;
64      size--;
65      i = 1;
66      for (; ; ) {
67        l = (i << 1);
68        r = (i << 1) + 1;
69        if ((l <= size) && (data[l].Key.CompareTo(data[i].Key) == -1)) {
70          smallest = l;
71        } else {
72          smallest = i;
73        }
74        if ((r <= size) && (data[r].Key.CompareTo(data[smallest].Key) == -1)) {
75          smallest = r;
76        }
77        if (smallest == i) break;
78        KNElement temp = data[i];
79        data[i] = data[smallest];
80        data[smallest] = temp;
81        i = smallest;
82      }
83    }
84
85    public void Insert(K key, V value) {
86      size++;
87      int hole = size;
88      while ((hole > 1) && (data[hole >> 1].Key.CompareTo(key) == 1)) {
89        data[hole] = data[hole >> 1];
90        hole = hole >> 1;
91      }
92      data[hole].Key = key;
93      data[hole].Value = value;
94    }
95
96    public void DecreaseKey(K key, V value) {
97      int pos = size;
98      while ((pos > 1) && (data[pos >> 1].Key.CompareTo(key) != 0)) {
99        pos = pos >> 1;
100      }
101      if (data[pos].Key.CompareTo(key) != 0) {
102        throw new InvalidOperationException("Key not found");
103      }
104      throw new NotImplementedException();
105    }
106
107
108
109    // reset size to 0 and fill data array with sentinels
110    private void Reset() {
111      size = 0;
112      K sup = supremum;
113      int cap = capacity;
114      for (int i = 1; i <= cap; i++) {
115        data[i].Key = sup;
116      }
117    }
118  }
119}
Note: See TracBrowser for help on using the repository browser.