patkovskyi

Untitled

Jul 11th, 2013
3,233
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace Algorithms.Lib
  5. {
  6.     /// <summary>
  7.     /// Doesn't support duplicate values!
  8.     /// Yes, this breaks Liskov's principle. Sorry, Barbara!
  9.     /// </summary>    
  10.     public class BinaryHeapWithUpdates<TKey, TValue> : BinaryHeap<TKey, TValue>
  11.     {
  12.         protected readonly Dictionary<TValue, int> HeapIndexes;
  13.  
  14.         public BinaryHeapWithUpdates(IComparer<TKey> comparer, IEqualityComparer<TValue> valueComparer) : base(comparer)
  15.         {
  16.             HeapIndexes = new Dictionary<TValue, int>(valueComparer);
  17.         }
  18.  
  19.         public void UpdateKey(TValue value, TKey newKey)
  20.         {
  21.             int index;
  22.             if (!HeapIndexes.TryGetValue(value, out index))
  23.             {
  24.                 throw new ArgumentException("Value was not found in the heap.");
  25.             }
  26.  
  27.             var oldKey = Keys[index];
  28.             int comp = Comparer.Compare(newKey, oldKey);
  29.             Keys[index] = newKey;
  30.             if (comp < 0)
  31.             {
  32.                 // decrease-key
  33.                 BubbleUp(index);
  34.             }
  35.             else if (comp > 0)
  36.             {
  37.                 // increase-key
  38.                 BubbleDown(index);
  39.             }
  40.         }
  41.  
  42.         public override void Insert(TKey key, TValue value)
  43.         {
  44.             HeapIndexes.Add(value, Keys.Count);
  45.             base.Insert(key, value);
  46.         }
  47.  
  48.         public override KeyValuePair<TKey, TValue> ExtractMin()
  49.         {
  50.             var min = base.ExtractMin();
  51.             HeapIndexes.Remove(min.Value);
  52.             return min;
  53.         }
  54.  
  55.         protected override void Swap(int i, int j)
  56.         {
  57.             HeapIndexes[Values[i]] = j;
  58.             HeapIndexes[Values[j]] = i;
  59.             base.Swap(i, j);            
  60.         }
  61.     }
  62.  
  63.     /// <summary>
  64.     /// Supports duplicate keys, but without stable ordering guarantee.
  65.     /// Stable ordering can be achieved by adding version counter to each node (as done in boost).
  66.     /// </summary>    
  67.     public class BinaryHeap<TKey, TValue>
  68.     {
  69.         protected readonly IComparer<TKey> Comparer;
  70.         protected readonly List<TKey> Keys;
  71.         protected readonly List<TValue> Values;
  72.  
  73.         public BinaryHeap(IComparer<TKey> comparer)
  74.         {
  75.             this.Comparer = comparer;
  76.             Keys = new List<TKey>();
  77.             Values = new List<TValue>();
  78.         }
  79.  
  80.         // O(N)
  81.         public static BinaryHeap<TKey, TValue> Build(IEnumerable<KeyValuePair<TKey, TValue>> elements, IComparer<TKey> comparer)
  82.         {
  83.             var heap = new BinaryHeap<TKey, TValue>(comparer);
  84.             foreach (var element in elements)
  85.             {
  86.                 heap.Keys.Add(element.Key);
  87.                 heap.Values.Add(element.Value);
  88.             }
  89.  
  90.             for (int i = (heap.Keys.Count - 2) >> 1; i >= 0; i--)
  91.             {
  92.                 heap.BubbleDown(i);
  93.             }
  94.  
  95.             return heap;
  96.         }
  97.  
  98.         // O(logN)
  99.         public virtual void Insert(TKey key, TValue value)
  100.         {
  101.             Keys.Add(key);
  102.             Values.Add(value);
  103.             BubbleUp(Keys.Count - 1);
  104.         }
  105.  
  106.         // O(logN)
  107.         public virtual KeyValuePair<TKey, TValue> ExtractMin()
  108.         {
  109.             if (Keys.Count == 0)
  110.             {
  111.                 throw new InvalidOperationException("Cannot extract minimum from empty heap.");
  112.             }
  113.  
  114.             var p = new KeyValuePair<TKey, TValue>(Keys[0], Values[0]);
  115.             Swap(0, Keys.Count - 1);
  116.             Keys.RemoveAt(Keys.Count - 1);
  117.             Values.RemoveAt(Values.Count - 1);
  118.             BubbleDown(0);
  119.             return p;
  120.         }
  121.  
  122.         protected virtual void Swap(int i, int j)
  123.         {
  124.             TKey tmpKey = Keys[i];
  125.             TValue tmpVal = Values[i];
  126.  
  127.             Keys[i] = Keys[j];
  128.             Values[i] = Values[j];
  129.  
  130.             Keys[j] = tmpKey;
  131.             Values[j] = tmpVal;
  132.         }
  133.  
  134.         protected void BubbleUp(int index)
  135.         {
  136.             while (index > 0)
  137.             {
  138.                 int parent = (index - 1) >> 1;
  139.  
  140.                 // stop condition: element is not less than it's parent
  141.                 if (Comparer.Compare(Keys[parent], Keys[index]) <= 0) return;
  142.                 Swap(index, parent);
  143.                 index = parent;
  144.             }
  145.         }
  146.  
  147.         // this is also called Heapify
  148.         protected void BubbleDown(int index)
  149.         {
  150.             int lastParent = (Keys.Count - 2) >> 1;
  151.             while (index <= lastParent)
  152.             {
  153.                 int left = (index << 1) + 1;
  154.                 int right = left + 1;
  155.                 int min = index;
  156.                 if (left < Keys.Count && Comparer.Compare(Keys[left], Keys[min]) <= 0) min = left;
  157.                 if (right < Keys.Count && Comparer.Compare(Keys[right], Keys[min]) <= 0) min = right;
  158.  
  159.                 // stop condition: index element is not less than both children
  160.                 if (min == index) return;
  161.                 Swap(index, min);
  162.                 index = min;
  163.             }
  164.         }
  165.     }
  166. }
RAW Paste Data