C# Data Structures and Algorithm assignment
A_h_m_a_d
Newfolder.zipNew folder/Heap.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Tester.cs { public class Heap<K, D> where K : IComparable<K> { // This is a nested Node class whose purpose is to represent a node of a heap. private class Node : IHeapifyable<K, D> { // The Data field represents a payload. public D Data { get; set; } // The Key field is used to order elements with regard to the Binary Min (Max) Heap Policy, i.e. the key of the parent node is smaller (larger) than the key of its children. public K Key { get; set; } // The Position field reflects the location (index) of the node in the array-based internal data structure. public int Position { get; set; } public Node(K key, D value, int position) { Data = value; Key = key; Position = position; } // This is a ToString() method of the Node class. // It prints out a node as a tuple ('key value','payload','index')}. public override string ToString() { return "(" + Key.ToString() + "," + Data.ToString() + "," + Position + ")"; } } // --------------------------------------------------------------------------------- // Here the description of the methods and attributes of the Heap<K, D> class starts public int Count { get; private set; } // The data nodes of the Heap<K, D> are stored internally in the List collection. // Note that the element with index 0 is a dummy node. // The top-most element of the heap returned to the user via Min() is indexed as 1. private List<Node> data = new List<Node>(); // We refer to a given comparer to order elements in the heap. // Depending on the comparer, we may get either a binary Min-Heap or a binary Max-Heap. // In the former case, the comparer must order elements in the ascending order of the keys, and does this in the descending order in the latter case. private IComparer<K> comparer; // We expect the user to specify the comparer via the given argument. public Heap(IComparer<K> comparer) { this.comparer = comparer; // We use a default comparer when the user is unable to provide one. // This implies the restriction on type K such as 'where K : IComparable<K>' in the class declaration. if (this.comparer == null) this.comparer = Comparer<K>.Default; // We simplify the implementation of the Heap<K, D> by creating a dummy node at position 0. // This allows to achieve the following property: // The children of a node with index i have indices 2*i and 2*i+1 (if they exist). data.Add(new Node(default(K), default(D), 0)); } // This method returns the top-most (either a minimum or a maximum) of the heap. // It does not delete the element, just returns the node casted to the IHeapifyable<K, D> interface. public IHeapifyable<K, D> Min() { if (Count == 0) throw new InvalidOperationException("The heap is empty."); return data[1]; } // Insertion to the Heap<K, D> is based on the private UpHeap() method public IHeapifyable<K, D> Insert(K key, D value) { Count++; Node node = new Node(key, value, Count); data.Add(node); UpHeap(Count); return node; } private void UpHeap(int start) { int position = start; while (position != 1) { if (comparer.Compare(data[position].Key, data[position / 2].Key) < 0) Swap(position, position / 2); position = position / 2; } } private void DownHeap(int start) { int rightChild,leftChild = start; while(start<Count) { leftChild = leftChild * 2; int smallChild = start; rightChild = leftChild + 1; if (comparer.Compare(data[rightChild].Key, data[leftChild].Key) < 0) smallChild = rightChild; if (comparer.Compare(data[start].Key, data[smallChild].Key) < 0) break; else Swap(start, smallChild); start = smallChild; } } // This method swaps two elements in the list representing the heap. // Use it when you need to swap nodes in your solution, e.g. in DownHeap() that you will need to develop. private void Swap(int from, int to) { Node temp = data[from]; data[from] = data[to]; data[to] = temp; data[to].Position = to; data[from].Position = from; } public void Clear() { for (int i = 0; i <= Count; i++) data[i].Position = -1; data.Clear(); data.Add(new Node(default(K), default(D), 0)); Count = 0; } public override string ToString() { if (Count == 0) return "[]"; StringBuilder s = new StringBuilder(); s.Append("["); for (int i = 0; i < Count; i++) { s.Append(data[i + 1]); if (i + 1 < Count) s.Append(","); } s.Append("]"); return s.ToString(); } // TODO: Your task is to implement all the remaining methods. // Read the instruction carefully, study the code examples from above as they should help you to write the rest of the code. public IHeapifyable<K, D> Delete() { // You should replace this plug by your code. Node node = null; if (Count == 0) throw new InvalidOperationException("The heap is empty."); else { node = data[1]; data[1] = data[Count]; Count--; DownHeap(1); } return node; //throw new NotImplementedException(); } // Builds a minimum binary heap using the specified data according to the bottom-up approach. public IHeapifyable<K, D>[] BuildHeap(K[] keys, D[] data) { throw new NotImplementedException(); } public void DecreaseKey(IHeapifyable<K, D> element, K new_key) { data[element.Position] = new Node(new_key, data[element.Position].Data, element.Position); UpHeap(element.Position); } public IHeapifyable<K, D> DeleteElement(IHeapifyable<K, D> element) { Node elem = data[element.Position]; data.RemoveAt(element.Position); return elem; } public IHeapifyable<K, D> KthMinElement(int k) { return data[k]; } } }
New folder/IHeapifyable.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Tester.cs { public interface IHeapifyable<K, D> { D Data { get; set; } K Key { get; set; } int Position { get; } } }
New folder/Tester.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Tester.cs { class Tester { private class IntAscendingComparer : IComparer<int> { public int Compare(int A, int B) { return Math.Sign(A - B); } } private class IntDescendingComparer : IComparer<int> { public int Compare(int A, int B) { return -1 * Math.Sign(A - B); } } static void Main(string[] args) { // ------------------------ test instance (begin) string[] names = new string[] { "Kelly", "Cindy", "John", "Andrew", "Richard", "Michael", "Guy", "Elicia", "Tom", "Iman", "Simon", "Vicky", "Kevin", "David" }; int[] IDs = new int[] { 1, 6, 5, 7, 8, 3, 10, 4, 2, 9, 14, 12, 11, 13 }; int[] certificateAdd = new int[] { 1, 2, 3, 4, 5, 3, 7, 2, 2, 10, 11, 12, 13, 14 }; int[] certificateDelete = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }; int[] certificateMinHeapBuild = new int[] { 1, 8, 6, 9, 5, 3, 7, 4, 2, 10, 11, 12, 13, 14 }; int[] certificateMaxHeapBuild = new int[] { 11, 10, 14, 4, 5, 12, 7, 8, 9, 2, 1, 6, 13, 3 }; // ------------------------ test instance (end) Heap<int, string> minHeap = null; Heap<int, string> maxHeap = null; IHeapifyable<int, string>[] nodes = null; string result = ""; // test 1 try { Console.WriteLine("\n\nTest A: Create a min-heap by calling 'minHeap = new Heap<int, string>(new IntAscendingComparer());'"); minHeap = new Heap<int, string>(new IntAscendingComparer()); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); result = result + "A"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 2 try { Console.WriteLine("\n\nTest B: Run a sequence of operations: "); for (int i = 0; i < Math.Min(names.Length, IDs.Length); i++) { Console.WriteLine("\nInsert a node with name {0} (data) and ID {1} (key).", names[i], IDs[i]); IHeapifyable<int, string> node = minHeap.Insert(IDs[i], names[i]); if (!(node.Position == certificateAdd[i] && minHeap.Count == i + 1)) throw new Exception("The min-heap has a wrong structure"); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); } result = result + "B"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 3 try { Console.WriteLine("\n\nTest C: Run a sequence of operations: "); for (int i = 0; i < certificateDelete.Length; i++) { Console.WriteLine("\nDelete the minimum element from the min-heap."); IHeapifyable<int, string> node = minHeap.Delete(); if (node.Key != certificateDelete[i]) throw new Exception("The extracted node has a wrong key"); if (minHeap.Count != certificateDelete.Length - i - 1) throw new Exception("The heap has a wrong number of elements"); if (certificateDelete.Length - i - 1 > 0) { if ((minHeap.Min().Key != certificateDelete[i + 1]) && (minHeap.Min().Position != 1)) throw new Exception("The min-heap has a wrong structure"); } Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); } result = result + "C"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 4 try { Console.WriteLine("\n\nTest D: Delete the minimum element from the min-heap."); IHeapifyable<int, string> node = minHeap.Delete(); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } catch (InvalidOperationException) { Console.WriteLine(" :: SUCCESS: InvalidOperationException is thrown because the min-heap is empty"); result = result + "D"; } catch (Exception) { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } // test 5 try { Console.WriteLine("\n\nTest E: Run a sequence of operations: "); Console.WriteLine("\nInsert a node with name {0} (data) and ID {1} (key).", names[0], IDs[0]); IHeapifyable<int, string> node = minHeap.Insert(IDs[0], names[0]); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nBuild the min-heap for the pair of key-value arrays with \n[{0}] as keys and \n[{1}] as data elements", String.Join(", ", IDs), String.Join(", ", names)); nodes = minHeap.BuildHeap(IDs, names); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } catch (InvalidOperationException) { Console.WriteLine(" :: SUCCESS: InvalidOperationException is thrown because the min-heap is not empty"); result = result + "E"; } catch (Exception) { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } // test 6 try { Console.WriteLine("\n\nTest F: Run a sequence of operations: "); Console.WriteLine("\nClear the min-heap."); minHeap.Clear(); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nBuild the min-heap for the pair of key-value arrays with \n[{0}] as keys and \n[{1}] as data elements", String.Join(", ", IDs), String.Join(", ", names)); nodes = minHeap.BuildHeap(IDs, names); if (minHeap.Count != certificateMinHeapBuild.Length) throw new Exception("The resulting min-heap has a wrong number of elements."); if (nodes.Length != certificateMinHeapBuild.Length) throw new Exception("The size of the resulting array returned by BuildHeap() is incorrect."); for (int i = 0; i < nodes.Length; i++) { if (!(nodes[i].Position == certificateMinHeapBuild[i])) throw new Exception("The min-heap has a wrong structure"); } result = result + "F"; Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 7 try { Console.WriteLine("\n\nTest G: Run a sequence of operations: "); IHeapifyable<int, string> node = nodes[nodes.Length - 1]; Console.WriteLine("\nDelete the minimum element from the min-heap."); minHeap.Delete(); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nDelete the minimum element from the min-heap."); minHeap.Delete(); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nRun DecreaseKey(node,0) for node {0} by setting the new value of its key to 0", node); minHeap.DecreaseKey(node, 0); if (minHeap.Count != certificateMinHeapBuild.Length - 2) throw new Exception("The resulting min-heap has a wrong number of elements"); if (!((node.Position == 1) && (minHeap.Min().Key == node.Key))) throw new Exception("The min-heap has a wrong structure"); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); result = result + "G"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 8 try { Console.WriteLine("\n\nTest H: Run a sequence of operations: "); Console.WriteLine("\nCreate a max-heap by calling 'maxHeap = new Heap<int, string>(new IntDescendingComparer());'"); maxHeap = new Heap<int, string>(new IntDescendingComparer()); Console.WriteLine(" :: SUCCESS: max-heap's state " + maxHeap.ToString()); Console.WriteLine("\nBuild the max-heap for the pair of key-value arrays with \n[{0}] as keys and \n[{1}] as data elements", String.Join(", ", IDs), String.Join(", ", names)); nodes = maxHeap.BuildHeap(IDs, names); if (maxHeap.Count != certificateMaxHeapBuild.Length) throw new Exception("The resulting max-heap has a wrong number of elements"); if (nodes.Length != certificateMaxHeapBuild.Length) throw new Exception("The size of the resulting array returned by BuildHeap() is incorrect."); for (int i = 0; i < nodes.Length; i++) { if (!(nodes[i].Position == certificateMaxHeapBuild[i])) throw new Exception("The max-heap has a wrong structure"); } result = result + "H"; Console.WriteLine(" :: SUCCESS: max-heap's state " + maxHeap.ToString()); } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: max-heap's state " + maxHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 9 try { Console.WriteLine("\n\nTest I: Run a sequence of operations: "); IHeapifyable<int, string> node = nodes[4]; Console.WriteLine("\nDelete the Richard element from the min-heap."); IHeapifyable<int, string> r = minHeap.DeleteElement(node); if (!r.Data.Equals(node.Data)) throw new Exception("The deleted node is the incorrect node."); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); if (minHeap.Count != certificateMinHeapBuild.Length - 3) throw new Exception("The resulting min-heap has a wrong number of elements"); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); result = result + "I"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 10 try { Console.WriteLine("\n\nTest J: Run a sequence of operations: "); Console.WriteLine("min-heap's state " + minHeap.ToString()); IHeapifyable<int, string> node = minHeap.KthMinElement(4); if (!node.Data.Equals("John")) throw new Exception("The 4th deleted node" + node.ToString() + " is the incorrect node."); Console.WriteLine(" :: SUCCESS: 4th Node is " + node.ToString()); if (minHeap.Count != certificateMinHeapBuild.Length - 3) throw new Exception("The resulting min-heap has a wrong number of elements"); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); result = result + "J"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } Console.WriteLine("\n\n ------------------- SUMMARY ------------------- "); Console.WriteLine("Tests passed: " + result); Console.ReadKey(); } } }
