1 |
|
---|
2 | using System;
|
---|
3 | namespace 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 | }
|
---|