Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1894: renamed heap implementations

File size: 2.7 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using HeuristicLab.Algorithms.GraphRouting.Interfaces;
5namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
6  public sealed class BinaryHeap<K, V> : IHeap<K, V>
7    where K : IComparable
8    where V : IComparable {
9    private class HeapElement {
10      public K Key { get; set; }
11      public V Value { get; set; }
12    }
13
14    private int capacity;
15    private int size;
16    private HeapElement[] data;
17
18    public BinaryHeap(int cap) {
19      size = 0;
20      capacity = cap;
21      data = new HeapElement[capacity];
22    }
23
24    public int Size {
25      get { return size; }
26    }
27
28    public void Insert(K key, V value) {
29      HeapElement elem = new HeapElement();
30      elem.Key = key;
31      elem.Value = value;
32      data[size] = elem;
33      HeapifyDown(size);
34      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[0].Key, data[0].Value);
42    }
43
44    public K PeekMinKey() {
45      return data[0].Key;
46    }
47
48    public V PeekMinValue() {
49      return data[0].Value;
50    }
51
52    public void RemoveMin() {
53      RemoveAt(0);
54    }
55
56    public void DecreaseKey(K key, V value) {
57      for (int i = 0; i < size; i++) {
58        if (data[i].Value.CompareTo(value) == 0) {
59          RemoveAt(i);
60          Insert(key, value);
61          break;
62        }
63      }
64    }
65
66    private void RemoveAt(int idx) {
67      if (size == 1) {
68        size--;
69      } else {
70        if (idx < size - 1) {
71          Swap(idx, size - 1);
72          HeapifyUp(idx);
73        }
74        size--;
75      }
76    }
77
78    private void HeapifyDown(int start) {
79      int i = start;
80      int j = (i - 1) / 2;
81      while (i > 0 && (data[i].Key.CompareTo(data[j].Key) == -1)) {
82        Swap(i, j);
83        i = j;
84        j = (i - 1) / 2;
85      }
86    }
87
88    private void HeapifyUp(int start) {
89      int idx = start;
90      int left = 2 * idx + 1;
91      int right = 2 * idx + 2;
92      while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
93             (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
94        if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
95          Swap(left, idx);
96          idx = left;
97        } else {
98          Swap(right, idx);
99          idx = right;
100        }
101        left = 2 * idx + 1;
102        right = 2 * idx + 2;
103      }
104    }
105
106    private void Swap(int i, int j) {
107      var elem = data[i];
108      data[i] = data[j];
109      data[j] = elem;
110    }
111  }
112}
Note: See TracBrowser for help on using the repository browser.