View difference between Paste ID: kkZn123m and xj0dqht0

 using System;
 using System.Collections.Generic;
 
 namespace Algorithms.Lib
 {
     /// <summary>
     /// Doesn't support duplicate values!
     /// Yes, this breaks Liskov's principle. Sorry, Barbara!
     /// </summary>
     public class BinaryHeapWithUpdates<TKey, TValue> : BinaryHeap<TKey, TValue>
     {
         protected readonly Dictionary<TValue, int> HeapIndexes;
 
         public BinaryHeapWithUpdates(IComparer<TKey> comparer, IEqualityComparer<TValue> valueComparer) : base(comparer)
         {
             HeapIndexes = new Dictionary<TValue, int>(valueComparer);
         }
 
         public void UpdateKey(TValue value, TKey newKey)
         {
             int index;
             if (!HeapIndexes.TryGetValue(value, out index))
             {
                 throw new ArgumentException("Value was not found in the heap.");
             }
 
             var oldKey = Keys[index];
             int comp = Comparer.Compare(newKey, oldKey);
             Keys[index] = newKey;
             if (comp < 0)
             {
                 // decrease-key
                 BubbleUp(index);
             }
             else if (comp > 0)
             {
                 // increase-key
                 BubbleDown(index);
             }
         }
 
         public override void Insert(TKey key, TValue value)
         {
             HeapIndexes.Add(value, Keys.Count);
             base.Insert(key, value);
         }
 
         public override KeyValuePair<TKey, TValue> ExtractMin()
         {
             var min = base.ExtractMin();
             HeapIndexes.Remove(min.Value);
             return min;
         }
 
         protected override void Swap(int i, int j)
         {
             HeapIndexes[Values[i]] = j;
             HeapIndexes[Values[j]] = i;
             base.Swap(i, j);
         }
     }
 
     /// <summary>
     /// Supports duplicate keys, but without stable ordering guarantee.
     /// Stable ordering can be achieved by adding version counter to each node (as done in boost).
     /// </summary>
     public class BinaryHeap<TKey, TValue>
     {
         protected readonly IComparer<TKey> Comparer;
         protected readonly List<TKey> Keys;
         protected readonly List<TValue> Values;
 
         public BinaryHeap(IComparer<TKey> comparer)
         {
             this.Comparer = comparer;
             Keys = new List<TKey>();
             Values = new List<TValue>();
         }
 
         // O(N)
         public static BinaryHeap<TKey, TValue> Build(IEnumerable<KeyValuePair<TKey, TValue>> elements, IComparer<TKey> comparer)
         {
             var heap = new BinaryHeap<TKey, TValue>(comparer);
             foreach (var element in elements)
             {
                 heap.Keys.Add(element.Key);
                 heap.Values.Add(element.Value);
             }
 
             for (int i = (heap.Keys.Count - 2) >> 1; i >= 0; i--)
             {
                 heap.BubbleDown(i);
             }
 
             return heap;
         }
 
         // O(logN)
         public virtual void Insert(TKey key, TValue value)
         {
             Keys.Add(key);
             Values.Add(value);
             BubbleUp(Keys.Count - 1);
         }
 
         // O(logN)
         public virtual KeyValuePair<TKey, TValue> ExtractMin()
         {
             if (Keys.Count == 0)
             {
                 throw new InvalidOperationException("Cannot extract minimum from empty heap.");
             }
 
             var p = new KeyValuePair<TKey, TValue>(Keys[0], Values[0]);
-            Keys[0] = Keys[Keys.Count - 1];
+            Swap(0, Keys.Count - 1);
-            Values[0] = Values[Values.Count - 1];
+
             Values.RemoveAt(Values.Count - 1);
             BubbleDown(0);
             return p;
         }
 
         protected virtual void Swap(int i, int j)
         {
             TKey tmpKey = Keys[i];
             TValue tmpVal = Values[i];
 
             Keys[i] = Keys[j];
             Values[i] = Values[j];
 
             Keys[j] = tmpKey;
             Values[j] = tmpVal;
         }
 
         protected void BubbleUp(int index)
         {
             while (index > 0)
             {
                 int parent = (index - 1) >> 1;
 
                 // stop condition: element is not less than it's parent
                 if (Comparer.Compare(Keys[parent], Keys[index]) <= 0) return;
                 Swap(index, parent);
                 index = parent;
             }
         }
 
         // this is also called Heapify
         protected void BubbleDown(int index)
         {
             int lastParent = (Keys.Count - 2) >> 1;
             while (index <= lastParent)
             {
                 int left = (index << 1) + 1;
                 int right = left + 1;
                 int min = index;
                 if (left < Keys.Count && Comparer.Compare(Keys[left], Keys[min]) <= 0) min = left;
                 if (right < Keys.Count && Comparer.Compare(Keys[right], Keys[min]) <= 0) min = right;
 
                 // stop condition: index element is not less than both children
                 if (min == index) return;
                 Swap(index, min);
                 index = min;
             }
         }
     }
 }