1 


2  using System;


3  using System.Collections.Generic;


4  using HeuristicLab.Algorithms.GraphRouting.Interfaces;


5  namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {


6  public sealed class BinHeap<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 BinHeap(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  }

