Guest User

pq

a guest
Jan 6th, 2014
503
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class PriorityQueue<T> : ICollection, IEnumerable<T> where T : IComparable<T>
  2. {
  3. public enum Type
  4. {
  5. MinHeap = 0,
  6. MaxHeap = 1
  7. };
  8.  
  9. private readonly List<T> _heap;
  10. private readonly Type _type;
  11.  
  12.  
  13. IComparer<T> Comparer { get; set; }
  14.  
  15. /// <summary>
  16. /// If you want to create MaxHeap you should implement IComparer(T) returning >0 when first item is lesser than second and less than zero
  17. /// when first item is greater than second item.
  18. /// </summary>
  19. /// <param name="comparer">Comparer</param>
  20. public PriorityQueue(IComparer<T> comparer)
  21. : this(comparer, new List<T>())
  22. {
  23.  
  24. }
  25.  
  26. public PriorityQueue(IComparer<T> comparer, int Capacity)
  27. : this(comparer, new List<T>(Capacity))
  28. {
  29.  
  30. }
  31.  
  32. public PriorityQueue(IComparer<T> comparer, IEnumerable<T> collection)
  33. {
  34. if (collection == null)
  35. throw new ArgumentNullException("Collection is null!");
  36.  
  37. this.Comparer = comparer;
  38. _heap = new List<T>(collection);
  39. InitializeHeap();
  40. }
  41.  
  42. private void InitializeHeap()
  43. {
  44. if (_heap.Any())
  45. {
  46. for (int i = _heap.Count - 1; i >= 0; --i)
  47. this.BubbleDown(i);
  48. }
  49. }
  50.  
  51. private int Parent(int index)
  52. {
  53. if (index <= 0)
  54. return -1;
  55.  
  56. return (index - 1) / 2;
  57. }
  58.  
  59. private int LeftChildren(int index)
  60. {
  61. int childrenId = (index << 1) + 1;
  62. if (childrenId >= _heap.Count)
  63. return -1;
  64.  
  65. return childrenId;
  66. }
  67.  
  68. private int RightChildren(int index)
  69. {
  70. int childrenId = index * 2 + 2;
  71. if (childrenId >= _heap.Count)
  72. return -1;
  73.  
  74. return childrenId;
  75. }
  76.  
  77. static void Swap(List<T> list, int first, int second)
  78. {
  79. T temp = list[first];
  80. list[first] = list[second];
  81. list[second] = temp;
  82. }
  83.  
  84. /// <summary>
  85. /// Iterative bubble up heap method. O(logn);
  86. /// </summary>
  87. /// <param name="index">Item index</param>
  88. private void BubbleUp(int index)
  89. {
  90. //int parentIndex = Parent(index);
  91. int parentIndex = (index - 1) >> 1;
  92.  
  93. if (parentIndex == -1)
  94. return;
  95. T item = _heap[index];
  96.  
  97. while ( Comparer.Compare(_heap[index], _heap[parentIndex]) < 0 )
  98. {
  99. _heap[index] = _heap[parentIndex];
  100.  
  101. index = parentIndex;
  102. _heap[index] = item;
  103.  
  104. parentIndex = (index - 1) >> 1;
  105. if (parentIndex == -1)
  106. break;
  107. }
  108.  
  109. }
  110.  
  111.  
  112. /// <summary>
  113. /// Iterative bubble down heap method. O(logn);
  114. /// </summary>
  115. /// <param name="index">Item index.</param>
  116. private void BubbleDown(int index)
  117. {
  118. int leftChildren = (index << 1) + 1;
  119. int rightChildren = (index << 1) + 2;
  120. int minItem = (rightChildren < _heap.Count && Comparer.Compare(_heap[leftChildren], _heap[rightChildren]) > 0) ? rightChildren : leftChildren;
  121. T item = _heap[index];
  122.  
  123. while (minItem < _heap.Count && Comparer.Compare(_heap[minItem], _heap[index]) < 0)
  124. {
  125. // swap - performance issue (same as Swap(_heap, minItem, index) )
  126. T tempItem = _heap[minItem];
  127. _heap[minItem] = _heap[index];
  128. _heap[index] = tempItem;
  129. //endswap
  130.  
  131. index = minItem;
  132.  
  133. leftChildren = (index << 1) + 1;
  134. rightChildren = (index << 1) + 2;
  135.  
  136. minItem = (rightChildren < _heap.Count && Comparer.Compare(_heap[leftChildren], _heap[rightChildren]) > 0) ? rightChildren : leftChildren;
  137. }
  138. }
  139.  
  140.  
  141. private void BubbleUpRecursive(int index)
  142. {
  143. int parentIndex = Parent(index);
  144.  
  145. if (parentIndex == -1)
  146. return;
  147.  
  148. if ( Comparer.Compare(_heap[parentIndex], _heap[index]) > 0)
  149. {
  150. Swap(_heap, parentIndex, index);
  151. BubbleUpRecursive(parentIndex);
  152. }
  153. }
  154. private void BubbleDownRecursive(int index)
  155. {
  156. int leftChild = LeftChildren(index);
  157. int rightChild = RightChildren(index);
  158. int minChild = 0;
  159.  
  160. if (index >= _heap.Count || (leftChild == -1 && rightChild == -1))
  161. return;
  162.  
  163. if (leftChild == -1)
  164. minChild = rightChild;
  165. else if (rightChild == -1)
  166. minChild = leftChild;
  167. else
  168. minChild = (Comparer.Compare(_heap[leftChild], _heap[rightChild]) >= 0) ? rightChild : leftChild;
  169.  
  170. if ( Comparer.Compare(_heap[minChild], _heap[index]) < 0 )
  171. {
  172. Swap(_heap, minChild, index);
  173. BubbleDownRecursive(minChild);
  174. }
  175. }
  176.  
  177.  
  178. public void Enqueue(T item)
  179. {
  180. _heap.Add(item);
  181. BubbleUp(_heap.Count - 1);
  182. }
  183.  
  184. public T Dequeue()
  185. {
  186. if (_heap.Count == 0)
  187. throw new InvalidOperationException("Queue is empty!");
  188. int lastIndex = _heap.Count - 1;
  189. T rootItem = _heap[0];
  190. Swap(_heap, 0, lastIndex);
  191. _heap.RemoveAt(lastIndex);
  192. if (_heap.Any())
  193. BubbleDown(0);
  194.  
  195. return rootItem;
  196. }
  197.  
  198. public T Peek()
  199. {
  200. if (_heap.Count == 0)
  201. throw new InvalidCastException("Queue is empty!");
  202. return _heap[0];
  203. }
  204.  
  205. public IEnumerator<T> GetEnumerator()
  206. {
  207. return _heap.GetEnumerator();
  208. }
  209.  
  210. IEnumerator IEnumerable.GetEnumerator()
  211. {
  212. return GetEnumerator();
  213. }
  214.  
  215. public void CopyTo(Array array, int index)
  216. {
  217. ((ICollection)_heap).CopyTo(array, index);
  218. }
  219.  
  220. public int Count
  221. {
  222. get { return _heap.Count; }
  223. }
  224.  
  225. public bool IsSynchronized
  226. {
  227. get { return false; }
  228. }
  229.  
  230. public object SyncRoot
  231. {
  232. get { throw new NotImplementedException(); }
  233. }
  234. }
RAW Paste Data