Free cookie consent management tool by TermsFeed Policy Generator

source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV3.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: 3.3 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  // Fast Binary Heap
9  public sealed class BinaryHeapV3<K, V> : IHeap<K, V> where K : IComparable {
10    private class KNElement {
11      public K Key { get; set; }
12      public V Value { get; set; }
13    }
14
15    private int capacity;
16    private K supremum;
17    private int size; // index of last used element
18    private KNElement[] data;
19
20    public BinaryHeapV3(K sup, K infimum, int cap) {
21      size = 0;
22      capacity = cap;
23      data = new KNElement[cap + 2];
24      for (int i = 0; i < cap + 2; i++) {
25        data[i] = new KNElement();
26      }
27      data[0].Key = infimum;
28      data[capacity + 1].Key = sup;
29      supremum = sup;
30      Reset();
31
32    }
33
34    public int Size {
35      get { return size; }
36    }
37
38    public KeyValuePair<K, V> PeekMin() {
39      if (size == 0) {
40        throw new InvalidOperationException("Heap is empty");
41      }
42      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
43    }
44
45    public K PeekMinKey() {
46      return data[1].Key;
47    }
48
49    public V PeekMinValue() {
50      return data[1].Value;
51    }
52
53    public void RemoveMin() {
54      // first move up elements on a min-path
55      int hole = 1;
56      int succ = 2;
57      int sz = size;
58      KNElement[] dat = data;
59
60      while (succ < sz) {
61        K key1 = dat[succ].Key;
62        K key2 = dat[succ + 1].Key;
63        if (key1.CompareTo(key2) > 0) {
64          succ++;
65          dat[hole].Key = key2;
66          dat[hole].Value = dat[succ].Value;
67        } else {
68          dat[hole].Key = key1;
69          dat[hole].Value = dat[succ].Value;
70        }
71        hole = succ;
72        succ <<= 1;
73      }
74
75      // bubble up rightmost element
76      K bubble = dat[sz].Key;
77      int pred = hole >> 1;
78      while (dat[pred].Key.CompareTo(bubble) > 0) {
79        //dat[hole] = dat[pred];
80        dat[hole].Key = dat[pred].Key;
81        dat[hole].Value = dat[pred].Value;
82
83        hole = pred;
84        pred >>= 1;
85      }
86
87      // finally move data to hole
88      dat[hole].Key = bubble;
89      dat[hole].Value = dat[sz].Value;
90
91      dat[size].Key = supremum; // mark as deleted
92      size = sz - 1;
93    }
94
95    public void Insert(K key, V value) {
96      KNElement[] dat = data;
97      size++;
98
99      int hole = size;
100      int pred = hole >> 1;
101      K predKey = dat[pred].Key;
102
103      while (predKey.CompareTo(key) > 0) {  // must terminate due to sentinel at 0
104        dat[hole].Key = predKey;
105        dat[hole].Value = dat[pred].Value;
106        hole = pred;
107        pred >>= 1;
108        predKey = dat[pred].Key;
109      }
110
111      // finally move data to hole
112      dat[hole].Key = key;
113      dat[hole].Value = value;
114    }
115
116    public void DecreaseKey(K key, V value) {
117      throw new NotImplementedException();
118    }
119
120    // reset size to 0 and fill data array with sentinels
121    private void Reset() {
122      size = 0;
123      K sup = supremum;
124      int cap = capacity;
125      for (int i = 1; i <= cap; i++) {
126        data[i].Key = sup;
127      }
128    }
129  }
130}
Note: See TracBrowser for help on using the repository browser.