public void BuildMaxHeap_AllSameNumber()
        {
            int[] array = {5, 5, 5, 5, 5, 5};
            Heap heap = new Heap(array);

            Assert.IsTrue(IsMaxHeap(heap.Queue, 0));
        }

        public void ContainsMinHeapTest()
        {
            Heap<char> actual = new Heap<char> {'g', 'r', 'a', 'n', 'v'};

            Assert.IsTrue(actual.Contains('a'));
            Assert.IsFalse(actual.Contains('l'));
        }

        static void Main(string[] args)
        {
            StreamReader reader = new StreamReader(@"C:\Users\Darsh\Documents\Visual Studio 2013\Projects\ProjectThree\ProjectThree\input.txt");
            Student student;
            Heap<Student> theHeap = new Heap<Student>();

            string sr = reader.ReadLine();//raid

            Student[] records = new Student[sr.Length];

            while (sr != null)// while there is still text
            {
                string[] delimiter = { ",", " " };
                string[] info = sr.Split(delimiter, StringSplitOptions.RemoveEmptyEntries);
                student = new Student(Convert.ToInt32(info[0]), Convert.ToDouble(info[1]));

                theHeap.Insert(student);//insert all data into the Heap
                sr = reader.ReadLine();
            }
            Console.WriteLine("Empty? {0}",theHeap.IsEmpty()); //false
            Console.WriteLine("Root: {0}",theHeap.GetRoot());

            theHeap.RemoveRoot();
            theHeap.Print(); //Prints out student id and gpa as min heap

            Console.WriteLine();
            Console.WriteLine("HEAPSORT!!");
            theHeap.HeapSort();//prints out the heap sort going from high to low

            Console.ReadKey();
        }

        public static void Dijkstra(List<Tuple<int, int>>[] adj, int source, out int[] dist, out int[] pred)
        {
            int inf = int.MaxValue;
            int N = adj.Length;
            dist = new int[N];
            pred = new int[N];
            for (int i = 0; i < N; i++)
                dist[i] = inf;
            dist[source] = 0;

            Heap<int, int> heap = new Heap<int, int>(N, true);
            heap.Push(source, 0);

            while (!heap.IsEmpty())
            {
                int u = heap.PeekData();
                if (dist[u] != heap.Pop().Priority) continue;
                foreach (var tuple in adj[u])
                {
                    int v = tuple.Item1;
                    int uvWeight = tuple.Item2;
                    if (dist[v] > dist[u] + uvWeight)
                    {
                        dist[v] = dist[u] + uvWeight;
                        pred[v] = u;
                        heap.Push(v, dist[v]);
                    }
                }
            }
        }

        /// <summary>
        /// De hoofdfunctie van de pathfinding.
        /// </summary>
        /// <param name="a">Start positie als AstarObject</param>
        /// <param name="b">Eind positie als AstarObject</param>
        /// <param name="T"> Het type weg waarin hij moet zoeken</param>
        /// <returns></returns>
        List<Point> FindRoadPath(Road a, Road b, RoadType T)
        {
            AstarObject[,] Set = new AstarObject[14, 9];
            for (int x = 0; x < 14; x++)
            {
                for (int y = 0; y < 9; y++)
                {
                    Set[x, y] = new AstarObject(x, y, this);
                }
            }

            Heap<AstarObject> OpenSet = new Heap<AstarObject>(14 * 9);
            HashSet<AstarObject> ClosedSet = new HashSet<AstarObject>();
            AstarObject Start = Set[a.X, a.Y];
            AstarObject End = Set[b.X, b.Y];
            OpenSet.Add(Start);

            while (OpenSet.Count > 0)
            {
                AstarObject CurrentLocation = OpenSet.RemoveFirst();

                ClosedSet.Add(CurrentLocation);

                if (CurrentLocation == End)
                {
                    return RetracePath(Start, End);
                    //Retracepath and stuff.
                }

                List<AstarObject> Neighbours = GetNeighbours(CurrentLocation, ref Set, NeighbourhoodType.Neumann, MapsizeXR, MapsizeYR);
                foreach (AstarObject neighbour in Neighbours)
                {
                    if (neighbour.RType != T || ClosedSet.Contains(neighbour))
                    {
                        continue;
                    }

                    int newMovementCostToNeighbour = CurrentLocation.gCost + GetDistance(CurrentLocation, neighbour);
                    if (newMovementCostToNeighbour < neighbour.gCost || !OpenSet.Contains(neighbour))
                    {
                        neighbour.gCost = newMovementCostToNeighbour;
                        neighbour.hCost = GetDistance(neighbour, End);
                        neighbour.parent = CurrentLocation;

                        if (!OpenSet.Contains(neighbour))
                        {
                            OpenSet.Add(neighbour);
                        }
                        else
                        {
                            OpenSet.UpdateItem(neighbour);
                        }

                    }

                }

            }
            return new List<Point>();
        }

        public void Simple()
        {
            var heap = new Heap<int>(HeapType.Minimum)
                           {
                               5
                           };

            Assert.AreEqual(heap.Count, 1);
            Assert.IsFalse(heap.IsEmpty);
            Assert.AreEqual(heap.Root, 5);

            heap.Add(2);
            Assert.AreEqual(heap.Count, 2);
            Assert.IsFalse(heap.IsEmpty);
            Assert.AreEqual(heap.Root, 2);

            heap.Add(3);
            Assert.AreEqual(heap.Count, 3);
            Assert.IsFalse(heap.IsEmpty);
            Assert.AreEqual(heap.Root, 2);

            Assert.AreEqual(heap.RemoveRoot(), 2);

            heap.Add(1);
            Assert.AreEqual(heap.Count, 3);
            Assert.IsFalse(heap.IsEmpty);
            Assert.AreEqual(heap.Root, 1);
        }

        public void Simple()
        {
            var heap = new Heap<int>(HeapType.Maximum);

            Assert.AreEqual(heap.Type, HeapType.Maximum);
            Assert.AreEqual(heap.Count, 0);
            Assert.IsTrue(heap.IsEmpty);

            heap = new Heap<int>(HeapType.Maximum, Comparer<int>.Default);

            Assert.AreEqual(heap.Type, HeapType.Maximum);
            Assert.AreEqual(heap.Count, 0);
            Assert.IsTrue(heap.IsEmpty);

            heap = new Heap<int>(HeapType.Maximum, 50);

            Assert.AreEqual(heap.Type, HeapType.Maximum);
            Assert.AreEqual(heap.Count, 0);
            Assert.IsTrue(heap.IsEmpty);

            heap = new Heap<int>(HeapType.Maximum, 50, Comparer<int>.Default);

            Assert.AreEqual(heap.Type, HeapType.Maximum);
            Assert.AreEqual(heap.Count, 0);
            Assert.IsTrue(heap.IsEmpty);
        }

 public AStar()
 {
     FOpenList = new Heap();
     FClosedList = new Heap();
     FSuccessors = new ArrayList();
     FSolution = new ArrayList();
 }

        public void Insert_MultipleBubbleToRoot()
        {
            Heap<int> heap = new Heap<int>(HeapType.Max)
            {
                List = new List<int>()
                {
                    150, // root
                    50,  // left child
                    100, // right child
                    45,  // left child of 50
                    40,  // right child of 50
                    95,  // left child of 100
                    90,  // right child of 100
                }
            };

            heap.Insert(200);

            Assert.AreEqual<int>(200, heap.List[0]);
            Assert.AreEqual<int>(150, heap.List[1]);
            Assert.AreEqual<int>(100, heap.List[2]);
            Assert.AreEqual<int>(50, heap.List[3]);
            Assert.AreEqual<int>(40, heap.List[4]);
            Assert.AreEqual<int>(95, heap.List[5]);
            Assert.AreEqual<int>(90, heap.List[6]);
            Assert.AreEqual<int>(45, heap.List[7]);
        }

        public void CopyConstructorWithStrategyTest()
        {
            List<string> collection = new List<string> { "Granville", "Barnett", "Luca", "Del", "Tongo" };
            Heap<string> actual = new Heap<string>(collection, Strategy.Max);

            Assert.AreEqual(5, actual.Count);
        }

    /* 1 Implement a class PriorityQueue<T> based
     * on the data structure "binary heap".
     * */
    static void Main(string[] args)
    {
        var heap = new Heap<int>();
        heap.Add(1);
        heap.Add(2);
        heap.Add(3);

        Debug.Assert(heap.SameContents(new[] { 1, 2, 3 }));
        Console.WriteLine(string.Join(",", heap));

        Debug.Assert(heap.ChopHead() == 3);
        Debug.Assert(heap.ChopHead() == 2);
        Debug.Assert(heap.ChopHead() == 1);
        Debug.Assert(heap.IsEmpty);

        // higher string means lower priority
        var pqueue = new PriorityQueue<string, string>((s1, s2) => -s1.CompareTo(s2));

        pqueue.Enqueue("18:00", "Buy food");
        pqueue.Enqueue("06:00", "Walk dog");
        pqueue.Enqueue("21:00", "Do homework");
        pqueue.Enqueue("09:00", "Go to work");
        pqueue.Enqueue("21:00", "Drink beer");

        Debug.Assert(pqueue.Count == 5);

        Debug.Assert(pqueue.Dequeue() == "Walk dog");
        Debug.Assert(pqueue.Dequeue() == "Go to work");
        Debug.Assert(pqueue.Dequeue() == "Buy food");
        Debug.Assert(new[] { "Do homework", "Drink beer" }.Contains(pqueue.Dequeue()));
        Debug.Assert(new[] { "Do homework", "Drink beer" }.Contains(pqueue.Dequeue()));
    }

        public void TestHeapSort()
        {
            Heap<int> h = new Heap<int>();
            h.Insert(500);
            h.Insert(100);
            h.Insert(200);
            h.Insert(50);
            h.Insert(1);
            h.Insert(420);
            h.Insert(3);
            h.Insert(250);
            h.Insert(5);
            h.Insert(499);

            int[] sortedItems = h.HeapSort();
            Assert.AreEqual(1, sortedItems[0]);
            Assert.AreEqual(3, sortedItems[1]);
            Assert.AreEqual(5, sortedItems[2]);
            Assert.AreEqual(50, sortedItems[3]);
            Assert.AreEqual(100, sortedItems[4]);
            Assert.AreEqual(200, sortedItems[5]);
            Assert.AreEqual(250, sortedItems[6]);
            Assert.AreEqual(420, sortedItems[7]);
            Assert.AreEqual(499, sortedItems[8]);
            Assert.AreEqual(500, sortedItems[9]);
        }

	IEnumerator FindPath(Vector3 startPos, Vector3 targetPos) 
	{
		
		Stopwatch sw = new Stopwatch();
		sw.Start();
		
		Vector3[] waypoints = new Vector3[0];
		bool pathSuccess = false;
		
		Node startNode = grid.NodeFromWorldPoint(startPos);
		Node targetNode = grid.NodeFromWorldPoint(targetPos);
		
		if (startNode.walkable && targetNode.walkable) 
		{
			Heap<Node> openSet = new Heap<Node>(grid.MaxSize);
			HashSet<Node> closedSet = new HashSet<Node>();
			openSet.Add(startNode);
			
			while (openSet.Count > 0) 
			{
				Node currentNode = openSet.RemoveFirst();
				closedSet.Add(currentNode);
				
				if (currentNode == targetNode) 
				{
					sw.Stop();
					print ("Path found: " + sw.ElapsedMilliseconds + " ms");
					pathSuccess = true;
					break;
				}
				
				foreach (Node neighbour in grid.GetNeighbours(currentNode)) 
				{
					if (!neighbour.walkable || closedSet.Contains(neighbour)) 
					{
						continue;
					}
					
					int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour) + neighbour.movementPenalty;
					if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) 
					{
						neighbour.gCost = newMovementCostToNeighbour;
						neighbour.hCost = GetDistance(neighbour, targetNode);
						neighbour.parent = currentNode;
						
						if (!openSet.Contains(neighbour))
							openSet.Add(neighbour);
						else
							openSet.UpdateItem (neighbour);
					}
				}
			}
		}
		yield return null;
		if (pathSuccess) {
			waypoints = RetracePath(startNode,targetNode);
		}
		requestManager.FinishedProcessingPath(waypoints,pathSuccess);
		
	}

    public int NthSuperUglyNumber(int n, int[] primes)
    {
        if(n == 1){ return 1; }
        if(primes == null || !primes.Any()){ return 1;}
        if(primes.Length == 1){ return (int)Math.Pow(primes[0],(n-1)); }

        var uglies = new int[n];
        uglies[0] = 1;
        var c = 1;

        var minHeap = new Heap(primes);

        while(c < n){
            var m = minHeap.GetMin();
            var prime = m.GetPrime(uglies);
            var index = m.UglyIndex;
            var possibility = m.Value;

            if(possibility != uglies[c-1]){
                uglies[c++] = possibility;
            }

            minHeap.ReplaceMin(uglies[index+1] * prime, index+1);
        }

        return uglies.Last();
    }

 public void FindPath(Grid _grid)
 {
     Node start = _grid.StartNode;
     Node end = _grid.EndNode;
     open = new Heap<Node>(_grid.GridMaxSize);
     close = new HashSet<Node>();
     open.Add(start);
     while (open.Count > 0)
     {
         Node current = open.GetFirst();
         if (current.GridBlock.Equals(end.GridBlock))
             return;
         foreach(Node p in _grid.GetNeighbours(current))
         {
             if (p.GridBlock.Type != GridBlock.BlockType.Obstacle || close.Contains(p))
                 continue;                                      
             int gCost = current.gCost + GetDistance(current, p);
             if(gCost < current.gCost || !open.Contains(p))
             {
                 p.gCost = gCost;
                 p.hCost = GetDistance(current, p);
                 p.Parent = current;
                 if (!open.Contains(p))
                     open.Add(p);
             }
         }
     }
 }

	void FindPath(Vector3 startPos, Vector3 targetPos) {  // performs A* search on the grid to find a path
        startPos = new Vector3(startPos.x + 8.0f, 0, startPos.z - 2.0f); // offsets
        targetPos = new Vector3(targetPos.x + 8.0f, 0, targetPos.z - 2.0f); // offsets

        Node startNode = grid.GetNodeFromWorldPoint(startPos);
        Node targetNode = grid.GetNodeFromWorldPoint(targetPos);

        if (targetNode.walkable == false) return; // don't try to path find if we're on an unwalkable area

		Heap<Node> openSet = new Heap<Node>(grid.MaxSize); 
        HashSet<Node> closedSet = new HashSet<Node>();

        openSet.Add(startNode);
        while(openSet.Count > 0) { // we still have nodes 
			Node currentNode = openSet.pop();
            closedSet.Add(currentNode);
            if(currentNode == targetNode) { // we've found exit
                RetracePath(startNode, targetNode);
                path = backTrackPath(startNode, targetNode);
                return;
            }
            foreach(Node n in grid.GetNeighbours(currentNode)) {
                if (!n.walkable || closedSet.Contains(n)) continue;
                int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, n);
                if(newMovementCostToNeighbour < n.gCost || !openSet.contains(n)) {
                    n.gCost = newMovementCostToNeighbour;
                    n.hCost = GetDistance(n, targetNode);
                    n.parent = currentNode;

                    if (!openSet.contains(n)) openSet.Add(n); // add our neighbour into open set
					else openSet.UpdateItem(n);
                }
            }
        }
    }

        public void HeapifyDown_SwapLeft()
        {
            Heap<int> heap = new Heap<int>(HeapType.Max)
            {
                List = new List<int>()
                {
                    25,
                    50,
                    10
                }
            };

            using (ShimsContext.Create())
            {
                int swappedChildIx = int.MinValue;
                int swappedParentIx = int.MinValue;

                ShimHeap<int>.AllInstances.SwapInt32Int32 = (h, childIx, parentIx) =>
                {
                    swappedChildIx = childIx;
                    swappedParentIx = parentIx;
                };

                heap.HeapifyDown();

                Assert.AreEqual<int>(1, swappedChildIx);
                Assert.AreEqual<int>(0, swappedParentIx);
            }
        }

 public TNodeMatrixAssign(TNode Parent, Heap<CellMatrix> Heap, int Ref, MNode Expression)
     : base(Parent)
 {
     this._expression = Expression;
     this._ref = Ref;
     this._mat = Heap;
 }

        public void ContainsMaxHeapTest()
        {
            Heap<int> actual = new Heap<int>(Strategy.Max) {23, 45, 1, 9, 12};

            Assert.IsTrue(actual.Contains(12));
            Assert.IsFalse(actual.Contains(99));
        }

 void calc()
 {
     Scanner cin = new Scanner();
     int n = cin.nextInt();
     int[] r = new int[n];
     int i, j;
     Dictionary<int, int> dic = new Dictionary<int, int>();
     for (i = 0; i < n; i++)
     {
         r[i] = cin.nextInt();
         if (!dic.ContainsKey(r[i])) dic[r[i]] = 0;
         dic[r[i]]++;
     }
     if (dic.Count < 3)
     {
         Console.WriteLine(0);
         return;
     }
     long MAX = (long)1e10;
     Heap h = new Heap(0);
     foreach (var item in dic)
     {
         h = meld(h, new Heap(MAX * item.Value + item.Key));
     }
     int[,] ret = new int[n, 3];
     int retnum = 0;
     for (j = 0; ; j++)
     {
         long[] num = new long[3];
         for (i = 0; i < 3; i++)
         {
             num[i] = h.val;
             h = meld(h.r, h.l);
         }
         if (num[2] < MAX) break;
         int[] nums = new int[3];
         for (i = 0; i < 3; i++)
         {
             nums[i] = (int)(num[i] % MAX);
             num[i] -= MAX;
         }
         for (i = 0; i < 3; i++)
         {
             h = meld(h, new Heap(num[i]));
         }
         Array.Sort(nums);
         Array.Reverse(nums);
         for (i = 0; i < 3; i++)
         {
             ret[j, i] = nums[i];
         }
         retnum++;
     }
     Console.WriteLine(retnum);
     for (i = 0; i < retnum; i++)
     {
         Console.WriteLine("{0} {1} {2}", ret[i, 0], ret[i, 1], ret[i, 2]);
     }
 }