BinaryHeapWithUpdates

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];
            Values[0] = Values[Values.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;
            }
        }
    }
}