source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinomialHeap.cs @ 8539

using System;
using System.Collections.Generic;
using HeuristicLab.Algorithms.GraphRouting.Interfaces;
namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
  public sealed class BinomialHeap<K, V> : IHeap<K, V>
    where K : IComparable
    where V : IComparable {
    private HeapElement<K, V> head;
    private int size;
    private Dictionary<V, HeapElement<K, V>> elems;

    public BinomialHeap() {
      this.elems = new Dictionary<V, HeapElement<K, V>>();
    }

    public BinomialHeap(HeapElement<K, V> elem, int size) {
      this.head = elem;
      this.size = size;
      this.elems = new Dictionary<V, HeapElement<K, V>>();
    }

    public int Size {
      get { return size; }
    }

    public void Insert(K key, V value) {
      HeapElement<K, V> elem = new HeapElement<K, V>(key, value);
      elems.Add(elem.Value, elem);
      BinomialHeap<K, V> heap = new BinomialHeap<K, V>(elem, 1);
      heap = Union(heap, this);
      head = heap.head;
      size++;
    }

    public KeyValuePair<K, V> PeekMin() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      HeapElement<K, V> elem = PeekMinElem();
      return new KeyValuePair<K, V>(elem.Key, elem.Value);
    }

    public K PeekMinKey() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      return PeekMinElem().Key;
    }

    public V PeekMinValue() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      return PeekMinElem().Value;
    }

    public void DecreaseKey(K key, V value) {
      HeapElement<K, V> elem = elems[value];
      elem.Key = key;
      HeapElement<K, V> y = elem;
      HeapElement<K, V> z = y.Parent;

      V tempVal;
      K tempKey;
      while ((z != null) && (y.Key.CompareTo(z.Key) < 0)) {
        tempVal = y.Value;
        tempKey = y.Key;

        y.Value = z.Value;
        y.Key = z.Key;

        z.Value = tempVal;
        z.Key = tempKey;

        y = z;
        z = y.Parent;
      }
    }

    public void RemoveMin() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }

      HeapElement<K, V> x = head;
      HeapElement<K, V> y = x.Sibling;
      HeapElement<K, V> pred = x;
      HeapElement<K, V> xPrev = null;

      while (y != null) {
        if (y.Key.CompareTo(x.Key) < 0) {
          x = y;
          xPrev = pred;
        }
        pred = y;
        y = y.Sibling;
      }

      if (x == head) {
        head = x.Sibling;
      } else {
        xPrev.Sibling = x.Sibling;
      }

      BinomialHeap<K, V> h = new BinomialHeap<K, V>();

      HeapElement<K, V> z = x.Child;
      while (z != null) {
        HeapElement<K, V> next = z.Sibling;
        z.Sibling = h.head;
        h.head = z;
        z = next;
      }

      BinomialHeap<K, V> newH = Union(this, h);
      head = newH.head;

      elems.Remove(x.Value);
      size--;
    }

    private HeapElement<K, V> Merge(BinomialHeap<K, V> heap1, BinomialHeap<K, V> heap2) {
      if (heap1.head == null) {
        return heap2.head;
      } else if (heap2.head == null) {
        return heap1.head;
      }

      HeapElement<K, V> head;
      HeapElement<K, V> tail;
      HeapElement<K, V> h1Next = heap1.head;
      HeapElement<K, V> h2Next = heap2.head;

      if (heap1.head.Degree <= heap2.head.Degree) {
        head = heap1.head;
        h1Next = h1Next.Sibling;
      } else {
        head = heap2.head;
        h2Next = h2Next.Sibling;
      }

      tail = head;

      while (h1Next != null && h2Next != null) {
        if (h1Next.Degree <= h2Next.Degree) {
          tail.Sibling = h1Next;
          h1Next = h1Next.Sibling;
        } else {
          tail.Sibling = h2Next;
          h2Next = h2Next.Sibling;
        }
        tail = tail.Sibling;
      }

      if (h1Next != null) {
        tail.Sibling = h1Next;
      } else {
        tail.Sibling = h2Next;
      }

      return head;
    }

    private BinomialHeap<K, V> Union(BinomialHeap<K, V> h1, BinomialHeap<K, V> h2) {
      HeapElement<K, V> elem = Merge(h1, h2);
      BinomialHeap<K, V> h = new BinomialHeap<K, V>(elem, 0);
      if (h.head == null) {
        return h;
      }
      h.size = h1.size + h2.size;

      HeapElement<K, V> xPrev = null;
      HeapElement<K, V> x = h.head;
      HeapElement<K, V> xNext = x.Sibling;

      while (xNext != null) {
        if ((x.Degree != xNext.Degree) || (xNext.Sibling != null && xNext.Sibling.Degree == x.Degree)) {
          xPrev = x;
          x = xNext;
        } else {
          if (x.Key.CompareTo(xNext.Key) <= 0) {
            x.Sibling = xNext.Sibling;
            Link(xNext, x);
          } else {
            if (xPrev == null) {
              h.head = xNext;
            } else {
              xPrev.Sibling = xNext;
            }
            Link(x, xNext);
            x = xNext;
          }
        }
        xNext = x.Sibling;
      }
      return h;
    }

    private void Link(HeapElement<K, V> y, HeapElement<K, V> z) {
      y.Parent = z;
      y.Sibling = z.Child;
      z.Child = y;
      z.Degree = z.Degree + 1;
    }

    private HeapElement<K, V> PeekMinElem() {
      HeapElement<K, V> min = head;
      HeapElement<K, V> next = min.Sibling;
      while (next != null) {
        if (min.Key.CompareTo(next.Key) > 0) {
          min = next;
        }
        next = next.Sibling;
      }
      return min;
    }

  }
  public class HeapElement<K, V> {
    public K Key;
    public V Value;
    public int Degree;
    public HeapElement<K, V> Parent;
    public HeapElement<K, V> Child;
    public HeapElement<K, V> Sibling;

    public HeapElement(K key, V value) {
      this.Key = key;
      this.Value = value;
      this.Parent = null;
      this.Child = null;
      this.Sibling = null;
      this.Degree = 0;
    }
  }
}