1  // http://stackoverflow.com/questions/102398/priorityqueueinnet/13776636#13776636


2 


3 


4  using System.Collections;


5  using System.Collections.Generic;


6  using System.Linq;


7  using System;


8 


9  public abstract class Heap<T> : IEnumerable<T> {


10  private const int InitialCapacity = 0;


11  private const int GrowFactor = 2;


12  private const int MinGrow = 1;


13 


14  private int _capacity = InitialCapacity;


15  private T[] _heap = new T[InitialCapacity];


16  private int _tail = 0;


17 


18  public int Count { get { return _tail; } }


19  public int Capacity { get { return _capacity; } }


20 


21  protected Comparer<T> Comparer { get; private set; }


22  protected abstract bool Dominates(T x, T y);


23 


24  protected Heap()


25  : this(Comparer<T>.Default) {


26  }


27 


28  protected Heap(Comparer<T> comparer)


29  : this(Enumerable.Empty<T>(), comparer) {


30  }


31 


32  protected Heap(IEnumerable<T> collection)


33  : this(collection, Comparer<T>.Default) {


34  }


35 


36  protected Heap(IEnumerable<T> collection, Comparer<T> comparer) {


37  if (collection == null) throw new ArgumentNullException("collection");


38  if (comparer == null) throw new ArgumentNullException("comparer");


39 


40  Comparer = comparer;


41 


42  foreach (var item in collection) {


43  if (Count == Capacity)


44  Grow();


45 


46  _heap[_tail++] = item;


47  }


48 


49  for (int i = Parent(_tail  1); i >= 0; i)


50  BubbleDown(i);


51  }


52  protected Heap(Heap<T> original) {


53  // clone;


54  this._capacity = original._capacity;


55  this._tail = original._tail;


56  this._heap = new T[original._heap.Length];


57  Array.Copy(original._heap, this._heap, this._heap.Length);


58  this.Comparer = original.Comparer;


59  }


60 


61  public void Add(T item) {


62  if (Count == Capacity)


63  Grow();


64 


65  _heap[_tail++] = item;


66  BubbleUp(_tail  1);


67  }


68 


69  private void BubbleUp(int i) {


70  if (i == 0  Dominates(_heap[Parent(i)], _heap[i]))


71  return; //correct domination (or root)


72 


73  Swap(i, Parent(i));


74  BubbleUp(Parent(i));


75  }


76 


77  public T GetMin() {


78  if (Count == 0) throw new InvalidOperationException("Heap is empty");


79  return _heap[0];


80  }


81 


82  public T ExtractDominating() {


83  if (Count == 0) throw new InvalidOperationException("Heap is empty");


84  T ret = _heap[0];


85  _tail;


86  Swap(_tail, 0);


87  BubbleDown(0);


88  return ret;


89  }


90 


91  private void BubbleDown(int i) {


92  int dominatingNode = Dominating(i);


93  if (dominatingNode == i) return;


94  Swap(i, dominatingNode);


95  BubbleDown(dominatingNode);


96  }


97 


98  private int Dominating(int i) {


99  int dominatingNode = i;


100  dominatingNode = GetDominating(YoungChild(i), dominatingNode);


101  dominatingNode = GetDominating(OldChild(i), dominatingNode);


102 


103  return dominatingNode;


104  }


105 


106  private int GetDominating(int newNode, int dominatingNode) {


107  if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))


108  return newNode;


109  else


110  return dominatingNode;


111  }


112 


113  private void Swap(int i, int j) {


114  T tmp = _heap[i];


115  _heap[i] = _heap[j];


116  _heap[j] = tmp;


117  }


118 


119  private static int Parent(int i) {


120  return (i + 1) / 2  1;


121  }


122 


123  private static int YoungChild(int i) {


124  return (i + 1) * 2  1;


125  }


126 


127  private static int OldChild(int i) {


128  return YoungChild(i) + 1;


129  }


130 


131  private void Grow() {


132  int newCapacity = _capacity * GrowFactor + MinGrow;


133  var newHeap = new T[newCapacity];


134  Array.Copy(_heap, newHeap, _capacity);


135  _heap = newHeap;


136  _capacity = newCapacity;


137  }


138 


139  public IEnumerator<T> GetEnumerator() {


140  return _heap.Take(Count).GetEnumerator();


141  }


142 


143  IEnumerator IEnumerable.GetEnumerator() {


144  return GetEnumerator();


145  }


146  }


147 


148  public class MaxHeap<T> : Heap<T> {


149  public MaxHeap()


150  : this(Comparer<T>.Default) {


151  }


152 


153  public MaxHeap(Comparer<T> comparer)


154  : base(comparer) {


155  }


156 


157  public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)


158  : base(collection, comparer) {


159  }


160 


161  public MaxHeap(IEnumerable<T> collection)


162  : base(collection) {


163  }


164  public MaxHeap(MaxHeap<T> original) : base(original) { }


165 


166  protected override bool Dominates(T x, T y) {


167  return Comparer.Compare(x, y) >= 0;


168  }


169  }


170 


171  public class MinHeap<T> : Heap<T> {


172  public MinHeap()


173  : this(Comparer<T>.Default) {


174  }


175 


176  public MinHeap(Comparer<T> comparer)


177  : base(comparer) {


178  }


179 


180  public MinHeap(IEnumerable<T> collection)


181  : base(collection) {


182  }


183 


184  public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)


185  : base(collection, comparer) {


186  }


187  public MinHeap(MinHeap<T> original) : base(original) { }


188 


189  protected override bool Dominates(T x, T y) {


190  return Comparer.Compare(x, y) <= 0;


191  }


192  } 
