Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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]);
- Swap(0, Keys.Count - 1);
- Keys.RemoveAt(Keys.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;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement