Dijkstra + MinHeap implementation

minheap.cs

    //Implemented from http://www.cs.uu.nl/docs/vakken/ds/HoorC/Heap.pdf
    public class MinHeap<T> where T : IComparable<T>
    {
        private readonly T[] A;
        private int n;

        public int Count { get { return n; } }

        public MinHeap(int size)
        {
            A = new T[size + 1];
            n = 0;
        }

        public void Insert(T k)
        {
            n++;
            A[n] = k;
            rootify(n);
            checkHeap();
        }

        public T ExtractMin()
        {
            var res = A[1];
            A[1] = A[n--];
            heapify(1);
            checkHeap();
            return res;
        }

        public bool IsHeap()
        {
            for (var i = 1; i <= n; i++)
            {
                if (!heap(i))
                    return false;
            }
            return true;
        }

        private int L(int i) { return i << 1; }
        private int R(int i) { return (i << 1) | 1; }
        private int P(int i) { return i >> 1; }

        private bool heap(int i)
        {
            return (!(L(i) <= n) || A[i].CompareTo(A[L(i)]) <= 0)  //(L(i) <= n) -> A[i] <= A[L(i)]
                && (!(R(i) <= n) || A[i].CompareTo(A[R(i)]) <= 0); //(R(i) <= n) -> A[i] <= A[R(i)]
        }

        private void swap(int i, int j)
        {
            var temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }

        private void heapify(int i)
        {
            var j = i;
            if (L(i) <= n && A[L(i)].CompareTo(A[j]) < 0) //A[L(i)] < A[j]
                j = L(i);
            if (R(i) <= n && A[R(i)].CompareTo(A[j]) < 0) //A[R(i)] < A[j]
                j = R(i);
            if (j != i)
            {
                swap(i, j);
                heapify(j);
            }
        }

        private void rootify(int i)
        {
            if (i == 1 || A[i].CompareTo(A[P(i)]) >= 0) //A[i] >= A[P(i)]
                return;
            swap(i, P(i));
            rootify(P(i));
        }

        private void decreaseKey(int i, T k)
        {
            if (A[i].CompareTo(k) >= 0) //A[i] >= k
            {
                A[i] = k;
                rootify(i);
            }
            checkHeap();
        }

        private void increaseKey(int i, T k)
        {
            if (A[i].CompareTo(k) <= 0) //A[i] <= k
            {
                A[i] = k;
                heapify(i);
            }
            checkHeap();
        }

        private void checkHeap()
        {
#if DEBUG
            Debug.Assert(IsHeap());
#endif
        }
    }

    public class MinPriorityQueue<T> //can get Max by reversing swapping the compare eg CompareTo * -1
    {
        private class Node : IComparable<Node>
        {
            public int Priority { get; private set; }
            public T Value { get; private set; }

            public Node(int priority, T value)
            {
                Priority = priority;
                Value = value;
            }

            public int CompareTo(Node other)
            {
                return Priority.CompareTo(other.Priority);
            }
        }

        private readonly MinHeap<Node> _minHeap;

        public int Count { get { return _minHeap.Count; } }
        public bool IsValid { get { return _minHeap.IsHeap(); } }

        public MinPriorityQueue(int size)
        {
            _minHeap = new MinHeap<Node>(size);
        }

        public void Add(int priority, T value)
        {
            _minHeap.Insert(new Node(priority, value));
        }

        public T ExtractMin()
        {
            return _minHeap.ExtractMin().Value;
        }
    }

    public class Graph<TNode> //weighted undirected graph (matrix for the edges) so memory: O(n*n) where n = numNodes
    {
        private readonly int _size;
        private readonly TNode[] _nodes;
        private readonly int[,] _edges;

        public Graph(int size)
        {
            _size = size;
            _nodes = new TNode[size];
            _edges = new int[size, size];
            for (var u = 0; u < _size; u++)
                for (var v = u + 1; v < _size; v++)
                    this[u, v] = -1;
        }

        public int Size { get { return _size; } }

        public TNode this[int index]
        {
            get { return _nodes[index]; }
            set { _nodes[index] = value; }
        }

        public int this[int u, int v]
        {
            get
            {
                Debug.Assert(_edges[u, v] == _edges[v, u]);
                return _edges[u, v];
            }
            set
            {
                _edges[u, v] = value;
                _edges[v, u] = value;
            }
        }

        public IEnumerable<int> AdjacentNodes(int u)
        {
            for (var v = 0; v < _size; v++)
                if (this[u, v] > -1)
                    yield return v;
        }

        public void Dijkstra(int source, out int[] prev, out int[] dist) //int = node index
        {
            prev = new int[Size];
            dist = new int[Size];
            var visited = new bool[Size];

            for (var v = 0; v < Size; v++)
            {
                prev[v] = -1;
                dist[v] = int.MaxValue;
                visited[v] = false;
            }

            dist[source] = 0;
            var Q = new MinPriorityQueue<int>(Size);
            Q.Add(0, source);

            while (Q.Count != 0)
            {
                var u = Q.ExtractMin();
                if (visited[u])
                    continue;
                visited[u] = true;
                foreach (var v in AdjacentNodes(u))
                {
                    var alt = dist[u] + this[u, v];
                    if (alt < dist[v])
                    {
                        dist[v] = alt;
                        prev[v] = u;
                        Q.Add(alt, v);
                    }
                }
            }
        }

        public string ToDot()
        {
            var result = new StringBuilder();
            result.AppendLine("graph UndirectedGraph {");
            for (var i = 0; i < _size; i++)
                result.AppendLine(string.Format("    n{0} [label=\"{0}:{1}\"]", i, this[i]));
            result.AppendLine();
            for (var u = 0; u < _size; u++)
                for (var v = u + 1; v < _size; v++)
                    if (this[u, v] > -1)
                        result.AppendLine(string.Format("    n{0} -- n{1} [label=\"{2}\"]", u, v, this[u, v]));
            result.AppendLine("}");
            return result.ToString();
        }
    }